Multi-Objective Reinforcement Learning Using Routed Ensembles and Trajectory Attribution

Multi-Objective Reinforcement Learning Using Routed Ensembles and Trajectory Attribution

arXiv:2610.35733v1 [cs.LG] 26 Oct 2026

Zhenshuo Zhang Northeastern University Boston, MA

Ruoxuan Xiong Emory University Atlanta, GA

Hongyang R. Zhang Northeastern University Boston, MA

Abstract Multi-objective reinforcement learning is a fundamental problem for modern AI, with applications spanning post-training, reasoning models, and robotic control. A central challenge is to learn policies that balance competing objectives, such as helpfulness versus honesty in safety and alignment, or speed versus energy in robotics. The optimal policy can vary sharply with objective-weighting combinations, and the extent of this variation depends crucially on the degree of conflict among objectives, making per-preference policy learning sample-inefficient. In this paper, we introduce objective-conflict coefficients and derive near-optimal regret bounds for online settings using this measure, thereby quantifying the impact of misalignment on learning efficiency. Then, we design routed ensemble policy learning, an algorithm that maintains a small set of basis policies and dynamically routes trajectories to the policy with the highest potential reward. Finally, we consider trajectory selection as another approach to mitigate objective conflict, and design a kernel surrogate trajectory attribution algorithm that estimates how feedback signals from a set of trajectories influence policy learning on other trajectories. The kernel can capture nonlinear interactions such as synergy and antagonism between trajectories. We evaluate our approach across diverse environments and benchmarks: routed ensembles improve average performance by 4.3% over baselines for online environments from Meta-World and MO-Gymnasium, and kernel surrogate attribution improves correlation with leave-one-out analysis over existing baselines by 50%. When applied to trajectory selection, kernel-based attribution yields a 27% improvement in reward over baseline attribution methods.

1

Introduction

Given m potentially competing objectives in a reinforcement learning (RL) environment, how can we learn a small set of policies that maximizes expected reward under any specified preference weighting? This problem is fundamental in multi-agent systems [29], and is ubiquitous in modern AI systems. In robotics, agents often need to balance speed and energy efficiency. In reinforcement learning with human feedback, reasoning models, and post-training, models are often evaluated under competing criteria such as helpfulness, safety, and honesty [20, 37]. A core challenge in multi-objective RL (MORL) is that the optimal policy can vary drastically with objective weight combinations. For example, even small changes in preference can lead to qualitatively different optimal policies [34, 55]. Prior work has focused on approximating the Pareto frontier of the optimal reward trade-offs [42, 52, 55], or learning one policy for each objective [44, 53], and it remains unclear whether or when transferring trajectories across objectives is effective. A key yet underexplored question is that the difficulty of learning across preferences is fundamentally tied to the degree of misalignment among objectives. When objective weightings are well aligned (e.g., rewarding both final and intermediate progress), additional objectives can facilitate learning, 40th Conference on Neural Information Processing Systems (NeurIPS 2026).

and data collected under one preference can benefit policy learning for others. When objectives are misaligned or adversarially-injected (e.g., RLHF with corrupted reward components), naive transfer can become inefficient or even harmful [20, 27]. This problem is especially acute in high-dimensional settings, making it a critical open challenge to identify objective alignment [21]. To address this challenge, we introduce a new theoretical framework based on measuring objective conflict coefficients that quantify the degree of misalignment among objectives through the χ2 divergence. Our analysis shows that this coefficient interacts with the coverability coefficient [46]— which captures how well a single exploration policy can cover the preference space—to determine the sample complexity of online MORL. Our regret bound generalizes single-objective results [1, 19, 46, 7, 9] and is the first to formalize how objective misalignment affects learning efficiency across preferences. Our theoretical framework builds on recent advances in transfer learning under distribution shifts [50]. However, the technical challenge in MORL lies in quantifying the discrepancy in policy learning. Our main result, Theorem 3.6, relies on a low-rank basis assumption, along with a coverability condition that ensures sufficient exploration of the basis. Motivated by our theoretical framework, we propose routed ensemble policy learning, an online algorithm for learning a small set of basis policies, which can be applied to a real-world RL environment. This algorithm alternates between two steps: (i) routing each trajectory to the basis policy with the highest expected return under the corresponding preference weight, and (ii) partitioning trajectories into disjoint clusters and updating each basis policy using its assigned trajectories with a standard policy learning algorithm such as proximal policy optimization. Next, we consider an alternative perspective for tackling objective conflicts, based on selecting trajectories. This motivates the problem of quantifying the influence of individual trajectories upon the learned optimal policy, a problem for which we term trajectory attribution. We design a scalable kernel-based trajectory attribution procedure that estimates how trajectories help or hinder policy learning. Our procedure fits a kernel ridge regression surrogate to approximate policy performance across trajectory subsets. This can capture both individual contributions and higher-order interactions between trajectories. These interactions are common in high-dimensional settings and often underlie unexpected transfer behavior [21]. However, they are not captured by first-order influence approximations such as influence functions [36], linear surrogate models [26, 56], or gradient-similarity-based analysis [45, 17]. Our approach goes beyond prior work by leveraging efficient approximations grounded in policy gradients and random projections [55]. The results from more accurate trajectory attribution can guide trajectory selection in downstream policy learning. Lastly, we empirically validate our approach on the Meta-World robotics benchmark and highdimensional MO-Gymnasium tasks. Our algorithm consistently outperforms multi-objective baselines, achieving a significant reduction in cumulative regret in environments with structured objective conflicts. Specifically, routed ensemble learning outperforms the strongest baseline by 4.3% on the Meta-World benchmark and achieves an 8% average improvement in hypervolume on MOGymnasium tasks. Similar results are also observed in reinforcement learning with human feedback (RLHF) settings. Additionally, kernel-based attribution provides a 50% improvement in terms of the Spearman correlations with ground-truth leave-one-out influence scores. When applied to downstream task selection, kernel-based selection yields a 27% higher reward than existing attribution baselines. We present detailed ablation studies to validate the theoretical insights from our proposed framework. For instance, after the routed ensemble procedure, the coverability metric drops from 1.3 for a single policy to 0.2 for the ensemble policies, indicating that routing mitigates the exploration bottleneck caused by objective conflicts. We also conduct a detailed analysis on the number of basis policies in the ensemble, as well as validate a low-rank basis assumption in our theoretical setup. In summary, the contributions of this paper are threefold. • First, we introduce a new theoretical framework for MORL based on a χ2 measure that we call the objective conflict coefficient. The theoretical result can be relaxed to a setting with an approximate low-rank basis, and we empirically evaluate this assumption in various real-world environments. • Second, we design two algorithms for tackling objective conflicts: (1) routed ensemble policy learning, and (2) kernel-based trajectory attribution to estimate inter-trajectory influence. • Third, we demonstrate significant gains in sample efficiency and robustness across diverse MORL benchmarks covering language modeling, robotic control, and RLHF settings. 2

For the rest of this paper, we begin by stating the formal problem setup in Section 2. Afterward, we present our theoretical framework and proposed approach to tackle objective conflicts in Section 3. We will present our experiments to validate our proposed algorithms in Section 4. Lastly, we discuss the related work in Section 5 and conclude in Section 6. We provide the omitted algorithmic description and proofs in Appendix A and B. Omitted experimental setup and empirical evaluations are provided in Appendix C.

2

Preliminaries

We consider an RL environment modeled as a multi-objective Markov decision process (MOMDP), defined by the tuple M = (S, A, Pr(· | ·, ·), r, Ω, fΩ , H), where S and A denote the state and action spaces, Pr(· | s, a) is the transition kernel, r : S × A → Rm is a vector-valued reward function with m ≥ 2 objectives, and H is the horizon. The preference space is denoted as Ω ⊆ Rm + . The scalarization operator fw maps the return vector to a scalar utility under preference w ∈ Ω. We evaluate performance under a target preference distribution w ∼ P.

A stochastic policy π ∈ Π maps states to action distributions, and induces a trajectory τ = (s0 , a0 , r0 , . . . , sH , aH , rH ), where ah ∼ π(· | sh ) and sh+1 ∼ Pr[· | sh , at ]. More generally, the policy can be time dependent π1 , · · · , πH with ah ∼ πh (· | sh ) and induces a trajectory similarly. PH The trajectory return is the cumulative reward vector G(τ ) = h=0 r(sh , ah ) ∈ Rm . The expected return of policy π from an initial distribution s0 ∼ ρ is given by J(π) = [G(τ )] ∈ Rm . E s0 ∼ρ,τ ∼π

We primarily focus on linear operators, and thus the policy’s expected return can be written as J (π; w) = ⟨w, J(π)⟩. We consider an episodic online MORL setting with episodes t = 1, . . . , T . At the beginning of episode t, the system designer has access to the history D(t−1) = {(τ (u) , wu )}t−1 u=1 and observes the current preference vector wt ∈ Ω. Based on (D(t−1) , wt ), a learner applies a possibly randomized policy learning algorithm to select a policy π (t) , interacts with the MOMDP for (t) (t) (t) (t) (t) (t) H horizons, and observes a trajectory τ (t) = (s0 , a0 , r0 , . . . , sH , aH , rH ). After T episodes, the learner collects a set of trajectories D = {(τ (t) , wt )}Tt=1 and aims to learn a preference-conditioned policy π(·; w) that attains high utility for target preferences w in the support of P. In this paper, we focus on learning an ensemble policy corresponding to a small set of π(·; w). Our theoretical framework builds on the notion of coverability, which is a complexity measure defined on a fixed policy class Π [1, 46]: dπ (s, a) , Ccov := inf sup max sup h µ∈∆(S×A) π∈Π h∈[H] (s,a) µh (s, a) where dπh (s, a) = Prπ (sh = s, ah = a) denotes the state-action probability under policy π, and the infimum is over sequences of µh ∈ ∆(S × A). Intuitively, Ccov captures how hard it is for a single exploration distribution to simultaneously cover the occupancy measures of all policies in Π, serving as a hardness measure for online exploration.

3

Our Approach

We first provide several examples to illustrate how multi-objective misalignment affects policy learning. We then formalize this observation through the notion of objective conflict coefficient and show how it interacts with coverability to derive online regret bounds. The regret bound is shown to be tight with a matching lower bound. These theoretical insights motivate our algorithm, routed ensemble policy learning, which learns a small set of basis policies and routes trajectories to the policies that give the highest reward. Lastly, to interpret objective conflict and routing behavior, we develop a kernel-surrogate trajectory attribution algorithm that quantifies how individual trajectories influence policy learning across preference weights. 3.1

Examples and motivation

We start with two common MOMDP use cases to motivate our theoretical framework. 3

−1 −2 −2

−1 r1

0

Linear Pareto Frontier

0

−9 −18

−18

−9 r1

0

Concave Pareto Frontier

−8 −16 −16

0 r2

0

r2

Clustered Objectives r2

r2

0

−8 r1

0

Concave Pareto Frontier

−5

−10

−15 −15

−10

r1

−5

0

Figure 1: We visualize the objective space returns (r1 , r2 ) for policies optimized under varying preference weights w ∈ [0, 1] in three canonical regimes — clustered, linear and concave Pareto frontier. Light yellow indicates that w is closer to 1, while dark blue indicates w is closer to 0. Example 3.1 (Learning the Pareto frontier of a MOMDP). The Pareto frontier consists of policies for which no objective can be improved without worsening at least one other objective. Formally, a policy π dominates π ′ (denoted π ≻ π ′ ) if Ji (π) ≥ Ji (π ′ ) for all objectives i ∈ [m], with strict inequality for at least one i, where Ji (π) is the i-th entry of J(π). Example 3.2 (Online exploration under corrupted objectives). Consider an MOMDP with m = 2, where r1 is the clean task reward and r2 may be corrupted (possibly adversarial). The target preference is w = [1, 0]⊤ , so the goal is to optimize r1 . However, if corruption is present, trajectories collected online may be influenced by the spurious signal in r2 . This motivates the need to identify corrupted trajectories and to attribute their alignment with w. We illustrate that learning in an MOMDP depends on how objectives relate to one another. In the two-objective case (m = 2), there are three canonical regimes, as shown in Figure 1: (i) aligned objectives, (ii) conflicting objectives with an (approximately) linear Pareto frontier, and (iii) conflicting objectives with a strictly concave frontier. Aligned objectives admit a single policy that is optimal for all preferences. Linear conflict is captured by two corner policies whose mixtures span the frontier. Concave conflict requires additional intermediate policies beyond the corner solutions. When m grows, different objectives can simultaneously fall into different regimes—some aligned, linearly conflicting, and others exhibiting concave trade-offs. These induce discontinuous shifts and make policy optimization harder. 3.2

Theoretical characterization through conflict coefficients

With the above examples in mind, next, we quantify how objective conflict impacts sample complexity in MORL. We assume that there exists a set of K latent basis policies that (approximately) represent optimal policies across preferences for w ∈ Ω. The number of basis policies K captures the intrinsic complexity of the objective trade-offs. We capture the extent of conflict via the objective conflict coefficient Γ, which measures the diversity of basis occupancies relative to their mixture. Definition 3.3. Let the basis-mixture occupancy be the uniform average of the K basis policies, ∗ PK πbk 1 dh (s, a) := K k=1 dh (s, a). The objective conflict coefficient is  ∗  π Γ := max max χ2 dhbk ∥dh . (1) h∈[H] k∈[K]

Smaller Γ indicates substantial overlap among basis policies and easier transfer across preferences, while large values correspond to near-disjoint occupancies and greater learning difficulty. Moreover, Γ is always bounded by K − 1 (Lemma B.5), so its magnitude scales with the number of basis policies. For instance, Γ = 0 in Case 1, and Γ is larger in Case 3 than in Case 2. We now analyze online MORL through cumulative regret: T   X ⋆ Reg(T ) = J (πw ; wt ) − J (π (t) ; wt ) . t t=1

We impose two structural assumptions. The first states that optimal policies lie in the convex hull of the basis occupancies. ⋆ Assumption 3.4. There exists a finite set of latent basis policies {π1⋆ , . . . , πK } such that for any K−1 w ∈ Ω, there exists a mixing vector νw ∈ ∆ (the probability simplex over K elements) satisfying PK π⋆ π⋆ dhw (s, a) = k=1 νw (k) dhbk (s, a) for all (s, a) ∈ S × A . 4

This assumption is imposed to yield a clean characterization of the role of K in regret. We relax this condition in Appendix B.4 by allowing optimal occupancies to lie within an ϵ-neighborhood of the convex hull, under which the same qualitative conclusions continue to hold. The second assumption ensures sufficient exploration of all basis components. (t)

Assumption 3.5. For each t ≥ 1, there exists ν (t) ∈ [0, 1]K such that dπh (s, a) = ⋆ PK Pt−1 (i) πbk 1 (t) (t) k=1 ν (k) dh (s, a) for all (s, a) and H. Letting ν (k) = t−1 i=1 ν (k), we assume (t) there exist c0 ∈ (0, 1] and a burn-in time t0 such that mink∈[K] ν (k) ≥ c0 /(Ccov K) for all t ≥ t0 . This condition holds, for example, when preferences are sampled with full support over Ω, ensuring persistent coverage of all basis policies. We now derive a regret bound that explicitly quantifies the impact of K and Γ. We study a Kpolicy variant of the optimistic confidence-set algorithm [19]. The learner maintains K confidence (t−1) sets Fk (β), one for each basis index k ∈ [K], and at episode t executes the optimistic policy (t−1) π (t) = πf (t) associated with some f (t) ∈ Fkt (β) for the routed basis kt . A detailed description is provided in Appendix B.1. Each Fk is given by Fk,1 ×· · ·×Fk,H , with Fk,h ⊆ (S ×A×Ω → [0, H]). We assume that Fk is finite and write |F| = maxk∈[K] |Fk |. For infinite classes, one can replace log |F| via covering numbers [19]. Our main result is stated as follows. Theorem 3.6. Suppose scalarized rewards are bounded in [0, 1] per step, Bellman realizability and completeness hold for each per-basis class Fk , and Assumptions 3.4–3.5 hold. Let β = c1 log(K|F |T /δ) be the confidence-set radius after a union bound across the K basis classes. After t0 = O(Ccov Kβ), then with probability at least 1 − δ, there exists an algorithm with K policies such that the cumulative regret satisfies  p  Reg(T ) ≤ OT H Ccov (1 + Γ) log(K |F| T δ −1 )T . (2)

Theorem 3.6 decomposes learning difficulty into (i) exploration hardness, governed by Ccov , and (ii) transfer hardness induced by objective conflict, captured by Γ. When objectives are well aligned, both Γ and K are small, and the regret approaches the single-objective rate; when basis occupancies are nearly disjoint, Γ increases, reflecting the cost of transferring information across preferences. The full proof of Theorem 3.6 is given in Appendix B.1. Nearly-tight regret lower bound. We complement this p upper bound
with a matching lower bound in Theorem B.6 in Appendix B.2, in the order of ΩT H (1 + Γ)T , establishing the tightness of the dependence on Γ and T up to Ccov and logarithmic factors. Remark 3.7. Although Theorem 3.6 is developed for a stylized online algorithm, similar proof techniques can be extended to more general settings. Proposition B.10 in Appendix B.4 shows that, when the low-rank basis Assumption 3.4 is relaxed to approximate low-rankness, the resulting regret bound preserves the same qualitative dependence on K and Γ. Furthermore, empirical analysis in Appendix C.2 demonstrates that these insights extend beyond the theoretical setting. To assess the approximation empirically, we measure the convex-hull residual over a preference grid. In a tabular concave setting, the mean residual decreases from 0.186 at K = 3 to 1.45 × 10−4 at K = 21; on MO-Hopper, it decreases from 0.443 at K = 3 to 0.231 at K = 15 using candidate-selected bases. The analysis below uses the exact assumption, while Appendix B.4 treats nonzero residuals. We also find that increasing the size of N gradually reduces the approximation error imposed by the low-rank condition (See Table 8 for the evaluation). 3.3

Learning routed ensemble policies

In Sections 3.1 and 3.2, the basis policies are assumed latent. Next, we design a scalable routed ensemble policy learning algorithm that: (i) explicitly learn a set of N basis policies, with each trajectory routed to the highest-reward basis, and (ii) learn a preference-conditioned transfer operator fw : ΠN → Π that maps these basis policies to a composite policy for any given preference w. 5

We also clarify that the ensemble size N may or may not be the same as K as stated in Assumption 3.4. Thus, the algorithms studied will apply to a real-world MORL environment. Our proposed Algorithm 1 alternates between scoring, routing, and updating: (i) Scoring: For each trajectory and each basis policy, compute a score using its estimated scalarized return (cf. Equation (4) below). (ii) Routing: Assign each trajectory to the basis policy that achieves the highest score for the corresponding preference, inducing a partition of the data into N clusters. (iii) Updating: Update each basis policy using only the trajectories assigned to its cluster via a standard RL subroutine (e.g., upper-confidence bound value iteration for MOMDPs [44]). (iv) Iteration: Repeat the above steps across online batches until both the cluster assignments and the learned policies stabilize. We formalize the learning objective as: "* +# H X max w, r(sh , fw ) , (3) E π1 ,π2 ,...,πN s0 ∼ρ,w∼P

h=0

which maximizes the expected scalarized return J (π; w) of the composed policy fw (π1 , . . . , πN ) under the target preference distribution P. Importantly, the routing step is optimal under this formulation: when fw lies in the convex hull of a fixed set of basis policies, the optimal solution reduces to deterministically selecting the basis policy that maximizes the return under w. This follows from the linearity of J (π; w) in w, and is formalized in the following lemma. Lemma 3.8. Fix a set of N policies {π1 , . . . , πN }. Suppose fw ∈ conv{π1 , . . . , πN } and PN dfhw (s, a) = i=1 αi (w)dπhi (s, a) for α(w) ∈ ∆N −1 . There exists an optimal routing function fb for Equation (3) such that, for every w ∈ Ω, fbw = πj , where j ∈ arg maxi∈{1,2,...,N } ⟨w, J(πi )⟩. Proof. For any w, since fw lies in the convex hull of π1 , . . . , πN , the state-action occupancy probaP bilities satisfy dfhw (s, a) = i αi (w)dπhi (s, a). Thus, the scalarized return satisfies X X f Jα (fw ) = dhw (sh , ah ) ⟨w, rh (s, a)⟩ h ah ,sh

=

N X X X h ah ,sh i=1

αi (w)dπhi (sh , ah ) ⟨w, rh (s, a)⟩ =

N X i=1

αi (w) ⟨J(πi ), w⟩ .

(4)

The maximum over α ∈ ∆N −1 is therefore attained at an extreme point, corresponding to selecting a single basis policy. Thus, the optimal strategy is to choose the policy πi that maximizes ⟨J(πi ), w⟩. Lemma 3.8 motivates the scoring and routing steps: we compute scores using equation (4) and route each trajectory to the basis policy that maximizes the score. Note that in the updating step, each basis policy is trained only on its assigned trajectories. This is crucial because a policy that performs well for one preference w may perform poorly for a different w′ . Consequently, mixing trajectories across preferences can degrade learning [44]. Moreover, Proposition B.8 in Appendix B.3 connects this algorithm to Γ, showing that the intuition underlying Theorem 3.6 carries over to its performance. Finally, while our algorithm assumes N is given, in practice it can be selected via cross-validation (Section 4.3). One may adaptively grow N by identifying new clusters when existing policies do not explain incoming trajectories, drawing on the clustering literature [8, 28]. Compared to previous work [44] that learns one optimal policy for each objective, the routed ensemble algorithm can leverage potential overlap that is latent in the underlying RL environment. 3.4

Trajectory attribution

Another approach to address the problem of objective conflict is through trajectory selection, for instance, removing trajectories that are far from the learned policy [55]. This motivates the question of quantifying how individual training trajectories contribute to policy performance, a problem that we term trajectory attribution. This complements our theoretical analysis above by providing a data-driven measure of which trajectories help or hinder learning and by improving the interpretability of routed ensemble policies. 6

Algorithm 1 Learning Routed Ensemble Policies for Multi-Objective Markov Decision Processes Input: A MOMDP M; Initial state distribution ρ; Preference distribution P; Number of policies N Require: A policy learning algorithm F ; A policy evaluation function J; Number of iterations T ; Horizon H; Number of observed trajectories B per iteration Output: A set of N policies (0)

(0)

(0)

1: π1 , π2 , . . . , πN : S → ∆(A), start from N random initializations 2: for t = 1, . . . , T do 3: wt ∼ P, Dt ← ∅, S ← N by B score matrix 4: for i = 1, . . . , B do 5: ji ← sample uniformly from {1, 2, . . . , N } 6: s0 ← ρ: sample from the initial state distribution 7:

8: 9:

(t)

(t−1)

τi ← (s0 , a0 , . . . , sH , aH ): simulate from s0 for H steps using πji for j = 1, . . . , N do E H D P P (t−1) Sj,i ← wt , r(sh , a)πj (sh , a) ▷ Score policy j on trajectory i h=0

a∈A

end for (t) Dt ← Dt ∪ {(τi , wt )} end for for j = 1, . .n. , N do o (t) 14: Dt,j ← (τi , wt ) ∈ Dt | j ∈ arg max Sj ′ ,i 1≤j ′ ≤N
(t) (t−1) 15: π j ← F πj , Dt,j 16: end for 17: end for (T ) (T ) (T ) 18: return π1 , π2 , . . . , πN

10: 11: 12: 13:

▷ Route trajectories to policy j ▷ Update policy j using algorithm F

A natural starting point for tackling trajectory attribution is via leave-one-out (LOO) retraining, which measures the change in performance when trajectory t is excluded:

ItLOO = V [1]T − V [1]T − et , 
 where, for any subset indicator S ∈ {0, 1}T , we define V(S) := Ew∼P J πS ; w , πS := F (DS ), with DS := {(τ (j) , wj ) ∈ D : Sj = 1}. Here πS is the policy trained on the subset selected by S using algorithm F , [1]T is the all-ones vector, and et is the t-th standard basis vector. Thus, ItLOO reflects the marginal importance of trajectory t. However, exact LOO retraining becomes computationally infeasible as the number of trajectories grows [26]. Moreover, it only captures one-at-a-time effects and misses nonlinear interactions among trajectories. To address these limitations, Algorithm 2 introduces a scalable kernel-surrogate approach [26, 56] that approximates the subset-performance function V(·). This procedure proceeds in three steps. First, we randomly sample n trajectory subsets S1 , . . . , Sn , where each Si ∈ {0, 1}T indicates which trajectories are included. Second, for each subset Si , we estimate its performance using a surrogate loss v(Si ) ≈ V(Si ). Third, we fit a kernel ridge regression surrogate: we form the radial basis function kernel Ψij = exp(−γ∥Si − Sj ∥2 ), set V = [b v (S1 ), . . . , vb(Sn )]⊤ , and compute −1 α = (Ψ + λ Idn ) V . This yields the predictor n X gα (S) = αi exp(−γ∥Si − S∥2 ), for V(S). i=1

Because this kernel model gα (S) is nonlinear in the subset indicator, it can capture higher-order interactions such as synergy and antagonism among trajectories. Provided with gα (S), we could then use this to score each trajectory; for instance, by averaging over all the subsets that include a particular trajectory. Then, trajectories with the highest scores are selected for downstream applications. The procedure above is formulated for trajectory attribution. However, the same procedure can be applied to objective attribution by sampling subsets of objectives. Each subset retains only the training contributions associated with its selected objectives. Removing an objective therefore excludes its contribution across all trajectories and allows us to estimate its effect on policy performance. 7

Algorithm 2 Kernel Surrogates for Trajectory Attribution Using Policy Gradient Estimation Input: A multi-objective RL environment with m reward objectives Requires: Subset sampling distribution D; Number of subsets n; ℓ2 -regularization parameter λ; A policy learning algorithm F m Output: A kernel surrogate model gθ : {0, 1} → R 1: θ ⋆ ← Learn a meta policy with all the m reward objectives simultaneously using F 2: S1 , . . . , Sn ← Sample n subsets from D independently 3: v b(S1 ), vb(S2 ), . . . , vb(Sn ) ← Apply P OLICY G RAD E X (Algorithm 3) with (S1 , S2 , . . . , Sn ; θ⋆ ) 2 4: Ψij ← exp(−γ ∥Si − Sj ∥ ), for all 1 ≤ i, j ≤ n ▷ Construct kernel matrix 5: V ← [b v (S1 ), . . . , vb(Sn )]⊤ ▷ Collect estimated outcomes 6: α ← (Ψ + λ IdnP )−1 V ▷ Fit kernel ridge regression n 2 7: return gθ (S) = α exp(−γ∥S − S∥ ) i i i=1 Implementation. In online RL, exact retraining for each sampled subset is often impractical because the training data evolve. We therefore estimate the subset performance v(Si ) locally around a reference policy trained on all trajectories. Specifically, we use policy gradients from local rollouts to approximate the parameter update induced by each subset, avoiding the cost of full retraining. The algorithm and the corresponding derivation are presented in Appendix A. The experimental results support this approximation. In Figure 3, Appendix C.2, we show that the fitted kernel model gα ([1]T − et ) is strongly positively correlated with the LOO scores ItLOO and strongly negatively correlated with the objective conflict coefficient Γ. Moreover, Algorithm 2 achieves a Spearman rank correlation of 0.75 with the true policy-gradient influence scores, confirming that it identifies influential trajectories. More details of the approximation procedure are presented in Appendix A.

4

Experiments

Our experiments are designed to address the following two aspects: (1) to verify the theoretical insights from the regret analysis, and (2) to evaluate the empirical performance of our algorithms across multi-objective RL settings, including synthetic environments, continuous robotic control, and RLHF settings. We highlight three findings. First, routing mitigates negative transfer and reduces cumulative regret in synthetic environments. Second, routed ensembles outperform baselines by a 4.3% relative margin in multi-task RL, up to 48% in multi-objective RL, and 17% in large language model benchmarks. Third, our kernel surrogates improve correlation with ground-truth marginal gains by 50% for trajectory attribution and improve downstream task-selection reward by 27%. Our code repository can be found at https://github.com/VirtuosoResearch/Multi-objective-reinforcement-learning-code/. 4.1

Evaluation in synthetic environments

We validate our theoretical insights in the following two environments (details can be found in Appendix C.1). 1. Learning Pareto frontier (Example 3.1). The environment has m = 4 conflicting objectives. The reward functions are designed such that maximizing one objective necessitates sacrificing the others, creating a complex, high-dimensional Pareto frontier. We sample preference vectors w uniformly from the simplex to evaluate the approximation of the frontier. 2. Learning under corrupted examples (Example 3.2). The environment has m = 2 objectives, where r1 represents a clean task signal and r2 represents a corrupted signal. The target preference is fixed at [1, 0], meaning the agent solves a single-objective problem but is exposed to conflicting gradients from r2 during exploration. The training preference is sampled uniformly in the simplex. 3. Routing under varying goal separation. We keep the environment dynamics fixed and vary the separation between goals. For each setting, we compute Γ from the resulting occupancies and measure the reduction in cumulative regret achieved by routing relative to the comparison method. 8

800

200 Best stationary policy MO-UCBVI Uniform Ensemble Routed Ensemble

Total regret

Total regret

1200

400 0

Best stationary policy MO-UCBVI Routed Ensemble Uniform Ensemble

100

0 1000 2000 Number of episodes

3000

0

(a) Learning Pareto frontier

1000 2000 Number of episodes

3000

(b) Learning under corrupted examples

Figure 2: We compare the cumulative regret of routed ensembles (red) against MO-UCBVI (green dashed), uniform ensembles (yellow), and the best stationary policy (blue dotted).

For Pareto frontier learning, Figure 2a shows that routed ensemble learning substantially reduces cumulative regret relative to MO-UCBVI [44], using one policy per objective. This suggests that routed ensembles maintain diverse basis policies that cover different regions of the frontier, while the single-policy baseline fails to capture the complex four-way trade-off. For learning under corrupted examples, Figure 2b shows that our approach mitigates negative transfer from corrupted inputs and achieves near-optimal performance. This suggests that routing can filter out harmful interference and assign trajectories to support optimization of the clean objective r1 . 4.2

Evaluation on robotic control and language models

Next, we present our evaluations applied to several robotic control and language modeling settings. We first describe the setups. Environments and models. We evaluate on four regimes, each with a different source of conflict: (i) shared dynamics on the 10-task MT10 benchmark from Meta-World [54]; (ii) explicit Pareto trade-offs on the continuous MO-HalfCheetah/Hopper/Ant and discrete Deep-Sea-Treasure/FruitTree environments of MO-Gymnasium [12]; (iii) preference-induced conflict on HelpSteer2 [43], with Qwen3-1.7B fine-tuned with PPO via per-basis LoRA adapters; and (iv) trajectory attribution on Multitask Minigrid, MT10, and a synthetic synergy MTRL environment (See Appendix C.1). In all regimes, routing is applied as a drop-in module on top of the published base learner. Baselines. We compare to the following baselines: (i) For multi-task RL, Soft Modularization [51], PaCo [39], CARE [38]; (ii) For continuous multi-objective RL, PGMORL [49], Q-Pensieve [18], CAPQL [31], GPI-LS [3], and learned-gate MoE; for discrete multi-objective RL, PQL [42], MPMOQL [42], and Envelop [52]; (iii) For RLHF, a single-policy model; (iv) For trajectory attribution, Influence Functions [23], TracIn [35] adapted to online RL setting [17], and linear surrogate models [26]. The MoE and GPI-LS comparisons hold the base policy-learning algorithm and interaction budget fixed to examine different routing and policy-selection mechanisms. For the first three regimes, we also include uniform assignment, which randomly assigns trajectories to basis policies. Evaluation. We use the following evaluation metrics: (i) success rate on MT10; (ii) hypervolume (HV) and utility (UT) on continuous MO-Gymnasium, and HV and cardinality (Card.) on discrete MO-Gymnasium; (iii) preference-induced conflict on HelpSteer2 [43] and UltraFeedback [10], using Qwen3-1.7B and Llama-3.2-1B fine-tuned with PPO via per-basis LoRA adapters; (iv) for trajectory attribution, linear data modeling score (LDS) and selection performance. LDS is the Spearman rank correlation between predicted and ground-truth marginal gains. Selection performance is the target objective return on a target objective when training within the top-3 most influential source tasks selected by each procedure. Results for policy optimization. Our proposed routed ensemble Algorithm 1 consistently outperforms baselines in multi-task and multi-objective settings. The comparison is presented in Table 1. On MT10, it achieves an average success rate of 85.6%, outperforming soft modularization (82.0%) by a relative margin of 4.3%. 9

Table 1: Comparison of our approach with several baseline methods. We report the average success rate on Meta-World, HV and UT on MuJoCo, as well as HV and Cardinality on Grid-World. Meta-World

MO-HalfCheetah2d MO-Hopper MO-Ant

Deep-Sea-Treasure Fruit-Tree

Algorithm 1

Metrics

Soft Modularization

PaCo

CARE

Uniform Assignment

Success rate

82.0±1.1 %

73.1±1.1 %

80.2±1.8 %

81.3±1.4 %

85.6±1.8 %

Metrics

PGMORL

Q-Pensieve

CAPQL

Uniform Assignment

Algorithm 1

HV (×106 ) UT (×102 ) HV (×107 ) UT (×102 ) HV (×107 ) UT (×102 )

0.11±0.08 0.12±0.13 1.23±0.04 0.04±0.02 0.17±0.11 0.21±0.06

4.85±0.06 2.14±0.13 1.61±0.32 1.47±0.14 1.83±0.28 1.75±0.02

3.29±0.18 0.63±0.09 1.39±0.13 1.29±0.12 0.84±0.05 1.76±0.16

3.17±0.11 1.01±0.12 1.56±0.16 1.17±0.09 1.81±0.15 1.68±0.08

5.17±0.16 2.47±0.14 1.83±0.14 1.56±0.06 2.03±0.16 1.82±0.12

Metrics

PQL

MPMOQL

Envelop

Uniform Assignment

Algorithm 1

HV (×103 ) Card. (×10) HV (×103 ) Card. (×10)

0.76±0.30 0.83±0.15 6.69±0.95 3.40±0.36

0.25±0.01 0.17±0.06 1.01±0.24 0.17±0.06

0.79±0.00 0.10±0.00 3.90±0.00 3.00±0.00

0.62±0.20 0.80±0.11 8.29±0.38 5.47±0.06

1.10±0.00 1.00±0.00 9.30±0.00 6.40±0.00

Table 2: Comparison results for RLHF settings between our approach, using a single policy, and uniform assignment to the same number of basis policies. Qwen3-1.7B

Synthetic Method Single Policy Uniform Assignment Algorithm 1

0.48 0.49 0.56

Llama-3.2-1B

HelpSteer2

UltraFeedback

HelpSteer2

UltraFeedback

0.51 0.47 0.54

0.46 0.47 0.48

0.34 0.35 0.35

0.52 0.54 0.55

Our routing algorithm also improves RLHF performance on both the synthetic environment and real-data benchmarks. In Table 2, we compare Algorithm 1, uniform assignment, and learning a single policy for each objective. Our algorithm consistently increases hypervolume on the induced frontier. In the synthetic environment, our method improves hypervolume by 17% over the single-policy baseline and 14% over the uniform ensemble. Averaged across the two models, the corresponding improvements are 5.0% and 8.2% on HelpSteer2, and 6.2% and 3.0% on UltraFeedback. Next, we present comparisons in continuous MO-Gymnasium environments in Table 3. Our routing algorithm yields an 8% average improvement over Q-Pensieve and achieves higher HV than learnedgate MoE and GPI-LS on all three benchmarks. The capacity-matched MoE comparison supports the benefit of trajectory routing beyond additional expert capacity. These results suggest that routing trajectories across basis policies helps distinguish aligned from conflicting data and approximates the Pareto frontier more efficiently than uniform assignment. Results for trajectory attribution. By applying Algorithm 2 at the objective level, we can achieve higher LDS scores and downstream task-selection performance. The results are presented in Table 5. The kernel surrogate improves LDS by 50% over attribution baselines across Multitask-Minigrid and MT10. Moreover, when used to select source tasks for co-training, kernel-surrogate attribution improves the target reward by 27%, demonstrating that the learned attributions are useful for downstream policy learning. 4.3

Ablation studies

Ensemble policies reduce coverability. We measure coverability using the union of state-action occupancies in the synthetic environment. A single policy results in a high χ2 -divergence of 1.3. The routed ensembles distribute exploration, reducing the metric to 0.2. This suggests that routing mitigates the exploration bottleneck. Varying the number of basis policies in the ensemble. We vary N in {2, 3, 4, 5} to evaluate the sensitivity of Algorithm 1 on three MuJoCo benchmarks. For MO-HalfCheetah-v4, the Hypervolumes are highest at 5.21 × 106 when N = 3. For MO-Hopper, it is 1.87 × 107 when N = 3. For MO-Ant, it is 2.12 × 107 when N = 5. See Appendix C.2 for the illustration of these ablation results. 10

Table 3: Hypervolume comparison with learned-gate Table 4: Measuring conflict and regret reducMoE and GPI-LS. tion under varying goal separation levels. Method

HalfCheetah2d

Hopper

Ant

Separation

Γ

Regret reduction

MoE GPI-LS Alg. 1

4.40±0.09 5.00±0.15 5.17±0.16

1.56±0.13 1.50±0.12 1.83±0.14

1.60±0.18 1.85±0.24 2.03±0.16

0 2 8

0.00±0.00 0.74±0.00 1.00±0.00

0.00±0.00 5.77±0.11 36.03±0.57

Table 5: We report the average target reward when the target policy is trained with source tasks selected by each attribution algorithm. Multitask Minigrid LDS Reward

Methods

Meta-World MT10 LDS Reward

Synergy MTRL LDS Reward

Influence functions TracIn Linear surrogates

−0.23±0.08 0.31±0.06 0.37±0.12

0.07±0.13 0.25±0.21 0.33±0.19

0.71±0.11 0.45±0.15 0.42±0.19

16.3±1.4 16.0±2.3 15.8±4.5

0.04±0.16 0.16±0.04 0.16±0.04

1.77±0.67 2.65±0.03 2.67±0.01

Algorithm 2

0.41±0.04

0.45±0.17

0.80±0.04

18.8±5.6

0.91±0.01

5.85±0.01

Nonlinear kernels improve trajectory attribution. We compare linear, quadratic, cubic, and RBF kernels by measuring the fitting loss of the kernel surrogate model in equation (5) on the synthetic dataset. The linear kernel converges to a loss of 0.2, while the quadratic, cubic, and RBF kernels all achieve a lower loss of 0.1. This gap demonstrates that the relationship between objective subsets and policy returns involves high-order interactions that a linear model cannot capture. From occupancy conflict to regret reduction. Lastly, we evaluate how occupancy conflict relates to regret reduction via routing in Table 4. We vary the separation between two reward goals. As goal separation increases, measured Γ rises from 0 to 1, while regret reduction from routing rises from 0 to 36.03. Across these settings, routing is more beneficial when preference-induced occupancies diverge. This trend is consistent with Theorem 3.6, where larger occupancy conflict increases the conflict-dependent term in the regret bound.

5

Related Work

A reinforcement learning environment is typically formalized by means of a Markov decision process [40, 2]. Existing approaches in the literature on multi-objective reinforcement learning (MORL) generally fall into two categories. The first reduces MORL to single-objective RL through scalarization, optimizing a fixed or sampled preference vector to learn a single policy [14, 33, 32, 38]. The second, which includes our work, examines the multi-objective nature of the problem by learning multiple policies (e.g., to approximate the Pareto frontier) to address sharp variation in optimal policies across preferences [42, 44, 30]. Recent work [55] proposes a convex relaxation algorithm for partitioning multiple objectives into disjoint, related groups. We build on this line of work by providing a theoretical characterization of objective conflicts in MORL, introducing a routed ensemble algorithm, and developing trajectory-level attribution to interpret model behavior. One interesting future direction is to examine the policy learning dynamics in multi-objective Markov decision processes [22, 24]. Lastly, sequential decision-making problems also occur in experimental design, where one often needs to roll out an experiment through staggered adoption [48, 47]. Recent work studies both offline and online RL with linear function approximation [15, 16]. It would be interesting to understand the techniques therein and examine whether it would be possible to extend to learning optimal policies under multiple objectives under linear Bellman completeness. More broadly, we refer the reader to a recent monograph by Foster and Rakhlin [13] for references. Influence estimation techniques [23, 35] have recently been extended from supervised learning to reinforcement learning to trace model behaviors. In the context of offline RL, [11] proposes a framework to attribute specific policy decisions to past trajectories. A fundamental challenge in the online RL setting is the circular dependency where current policy updates influence future data distribution. Recent work [17] addresses this by employing local data attribution via gradient similarity to identify and filter harmful transitions. 11

6

Conclusion

In this paper, we study how to learn policies that balance competing objectives in multi-objective reinforcement learning. We first analyze the theoretical limits of transfer learning across preferences, highlighting that structural misalignment between objectives is the primary cause of negative transfer. To overcome this challenge, we propose a routed ensemble algorithm guided by a new measure, the objective conflict coefficient. Furthermore, we introduce a kernel-based trajectory-attribution method that captures widespread nonlinear interactions among trajectories and can improve subsequent policy learning. The experimental results demonstrate that our approach achieves superior sample efficiency and attribution accuracy compared to state-of-the-art baselines across diverse benchmarks. One limitation of our theoretical framework is that the regret bounds do not directly apply to the routed ensemble algorithm. Further understanding the sample complexity of learning ensemble policies in multi-objective Markov decision processes is an interesting question for future work.

Acknowledgment We are grateful to the anonymous reviewers for their constructive comments that greatly improved this paper. Thanks to Dongruo Zhou for pointing out references to prior work. This work received financial assistance from NSF award IIS-2412008 and a startup fund from Northeastern University. Zhenshuo Zhang received additional financial support from Northeastern University’s Khoury PhD fellowships. R. Xiong is supported in part by the URC award at Emory University.

References [1] [2]

[3]

[4] [5] [6]

[7] [8] [9]

[10]

[11]

[12]

A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun. “Reinforcement learning: Theory and algorithms”. In: CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep 32 (2019), p. 96. A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. “On the theory of policy gradient methods: Optimality, approximation, and distribution shift”. In: Journal of Machine Learning Research 22.98 (2021), pp. 1–76. L. N. Alegre, A. L. Bazzan, D. M. Roijers, A. Nowé, and B. C. da Silva. “Sample-efficient multi-objective learning via generalized policy improvement prioritization”. In: arXiv preprint arXiv:2301.07784 (2023). M. Bateni, V. Cohen-Addad, Y. Gu, S. Lattanzi, S. Meierhans, and C. Mohri. “Algorithmic Thinking Theory”. In: arXiv preprint arXiv:2512.04923 (2025). A. Beygelzimer, S. Kale, and H. Luo. “Optimal and adaptive algorithms for online boosting”. In: International Conference on Machine Learning. PMLR. 2015, pp. 2323–2331. E. Chen, N. Dullerud, T. Niedermayr, E. Kidd, R. Senanayake, P. W. Koh, S. Koyejo, and C. Guestrin. “MoSH: Modeling Multi-Objective Tradeoffs with Soft and Hard Bounds”. In: arXiv preprint arXiv:2412.06154 (2024). F. Chen, Z. Jia, A. Rakhlin, and T. Xie. “Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits”. In: arXiv preprint arXiv:2505.20268 (2025). J. Chen, E. Sadeqi Azer, and Q. Zhang. “A practical algorithm for distributed clustering and outlier detection”. In: Advances in Neural Information Processing Systems 31 (2018). Y. Chi, Y. Chen, and Y. Wei. “Statistical and algorithmic foundations of reinforcement learning”. In: Tutorials in Operations Research: Advances in Analytics and Operations Research: Improving Decisions to Secure the Future. INFORMS, 2025, pp. 104–144. G. Cui, L. Yuan, N. Ding, G. Yao, B. He, W. Zhu, Y. Ni, G. Xie, R. Xie, Y. Lin, Z. Liu, and M. Sun. “Ultrafeedback: Boosting language models with scaled AI feedback”. In: arXiv preprint arXiv:2310.01377 (2023). S. V. Deshmukh, A. Dasgupta, B. Krishnamurthy, N. Jiang, C. Agarwal, G. Theocharous, and J. Subramanian. “Explaining RL Decisions with Trajectories”. In: The Eleventh International Conference on Learning Representations. 2023. F. Felten, L. N. Alegre, A. Nowé, A. L. C. Bazzan, E. G. Talbi, G. Danoy, and B. C. d. Silva. “A Toolkit for Reliable Benchmarking and Research in Multi-Objective Reinforcement Learning”. In: Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS 2023). 2023. 12

[13] D. J. Foster and A. Rakhlin. “Foundations of reinforcement learning and interactive decision making”. In: arXiv preprint arXiv:2312.16730 (2023). [14] Z. Gábor, Z. Kalmár, and C. Szepesvári. “Multi-criteria reinforcement learning.” In: ICML. Vol. 98. 1998, pp. 197–205. [15] N. Golowich and A. Moitra. “Linear bellman completeness suffices for efficient online reinforcement learning with few actions”. In: The Thirty Seventh Annual Conference on Learning Theory. PMLR. 2024, pp. 1939–1981. [16] N. Golowich and A. Moitra. “The role of inherent bellman error in offline reinforcement learning with linear function approximation”. In: Reinforcement Learning Conference. 2024. [17] Y. Hu, F. Wu, H. Ye, D. Forsyth, J. Zou, N. Jiang, J. W. Ma, and H. Zhao. “A Snapshot of Influence: A Local Data Attribution Framework for Online Reinforcement Learning”. In: The Thirty-ninth Annual Conference on Neural Information Processing Systems. 2025. [18] W. Hung, B.-K. Huang, P.-C. Hsieh, and X. Liu. “Q-Pensieve: Boosting Sample Efficiency of Multi-Objective RL Through Memory Sharing of Q-Snapshots”. In: arXiv preprint arXiv:2212.03117 (2022). [19] C. Jin, Q. Liu, and S. Miryoosefi. “Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms”. In: Advances in neural information processing systems 34 (2021), pp. 13406–13418. [20] M. Joglekar, J. Chen, G. Wu, J. Yosinski, J. Wang, B. Barak, and A. Glaese. “Training LLMs for Honesty via Confessions”. In: arXiv preprint arXiv:2512.08093 (2025). [21] V. Joshi, Z. Xu, B. Liu, P. Stone, and A. Zhang. “Benchmarking Massively Parallelized MultiTask Reinforcement Learning for Robotics Tasks”. In: Reinforcement Learning Conference. 2025. [22] S. M. Kakade. “A natural policy gradient”. In: Advances in neural information processing systems 14 (2001). [23] P. W. Koh and P. Liang. “Understanding black-box predictions via influence functions”. In: International conference on machine learning. PMLR. 2017, pp. 1885–1894. [24] G. Lan. “Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes: G. Lan”. In: Mathematical programming 198.1 (2023), pp. 1059–1106. [25] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. [26] D. Li, H. Nguyen, and H. R. Zhang. “Identification of Negative Transfers in Multitask Learning Using Surrogate Models”. In: Transactions on Machine Learning Research (2023). [27] D. Li, Z. Zhang, L. Wang, and H. R. Zhang. “MoPLEx: Estimating Plackett-Luce Mixture Models for Multi-Objective Alignment”. In: arXiv preprint arXiv:2608.25200 (2026). [28] Y. Li, Y. Song, and Q. Zhang. “Learning to cluster via same-cluster queries”. In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021, pp. 978–987. [29] M. L. Littman. “Markov games as a framework for multi-agent reinforcement learning”. In: Machine learning proceedings 1994. Elsevier, 1994, pp. 157–163. [30] E. Liu, Y.-C. Wu, X. Huang, C. Gao, R.-J. Wang, K. Xue, and C. Qian. “Pareto set learning for multi-objective reinforcement learning”. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 39. 18. 2025, pp. 18789–18797. [31] H. Lu, D. Herman, and Y. Yu. “Multi-objective reinforcement learning: Convexity, stationarity and pareto optimality”. In: The Eleventh International Conference on Learning Representations. 2023. [32] S. Mannor and N. Shimkin. “A geometric approach to multi-criterion reinforcement learning”. In: Journal of machine learning research 5.Apr (2004), pp. 325–360. [33] K. Miettinen and M. M. Mäkelä. “On scalarizing functions in multiobjective optimization”. In: OR spectrum 24.2 (2002), pp. 193–213. [34] C. H. Papadimitriou and M. Yannakakis. “On the approximability of trade-offs and optimal access of web sources”. In: Proceedings 41st annual symposium on foundations of computer science. IEEE. 2000, pp. 86–92. [35] G. Pruthi, F. Liu, S. Kale, and M. Sundararajan. “Estimating training data influence by tracing gradient descent”. In: Advances in Neural Information Processing Systems 33 (2020), pp. 19920–19930. 13

[36] I. Rubinstein and S. B. Hopkins. “On the Accuracy of Newton Step and Influence Function Data Attributions”. In: arXiv preprint arXiv:2512.12572 (2025). [37] S. Sengupta, G. Liu, O. Gottesman, J. W. Durham, M. Kearns, A. Roth, and M. Caldara. “Multi-Objective Reinforcement Learning for Large-Scale Tote Allocation in Human-Robot Collaborative Fulfillment Centers”. In: arXiv preprint arXiv:2602.24182 (2026). [38] S. Sodhani, A. Zhang, and J. Pineau. “Multi-task reinforcement learning with context-based representations”. In: International Conference on Machine Learning. 2021, pp. 9767–9779. [39] L. Sun, H. Zhang, W. Xu, and M. Tomizuka. “Paco: Parameter-compositional multi-task reinforcement learning”. In: Advances in Neural Information Processing Systems 35 (2022), pp. 21495–21507. [40] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. Second. Adaptive Computation and Machine Learning series. MIT Press, 2018. [41] M. Towers, A. Kwiatkowski, J. Terry, J. U. Balis, G. De Cola, T. Deleu, M. Goulão, A. Kallinteris, M. Krimmel, A. KG, R. Perez-Vicente, A. Pierré, S. Schulhoff, J. J. Tai, H. Tan, and O. G. Younis. “Gymnasium: A standard interface for reinforcement learning environments”. In: NeurIPS Datasets and Benchmarks (2025). [42] K. Van Moffaert and A. Nowé. “Multi-objective reinforcement learning using sets of pareto dominating policies”. In: The Journal of Machine Learning Research (2014), pp. 3483–3512. [43] Z. Wang, Y. Dong, O. Delalleau, J. Zeng, G. Shen, D. Egert, J. J. Zhang, M. N. Sreedhar, and O. Kuchaiev. “Helpsteer 2: Open-source dataset for training top-performing reward models”. In: Advances in Neural Information Processing Systems 37 (2024), pp. 1474–1501. [44] J. Wu, V. Braverman, and L. Yang. “Accommodating picky customers: Regret bound and exploration complexity for multi-objective reinforcement learning”. In: Advances in Neural Information Processing Systems 34 (2021), pp. 13112–13124. [45] S. Wu, H. R. Zhang, and C. Ré. “Understanding and improving information transfer in multitask learning”. In: ICLR (2020). [46] T. Xie, D. J. Foster, Y. Bai, N. Jiang, and S. M. Kakade. “The Role of Coverage in Online Reinforcement Learning”. In: The Eleventh International Conference on Learning Representations. 2023. [47] R. Xiong. “Automated experimental design with optimization from historical data simulations”. In: Available at SSRN 5126080 (2025). [48] R. Xiong, A. Chin, and S. J. Taylor. “Data-driven switchback experiments: Theoretical tradeoffs and empirical bayes designs”. In: arXiv preprint arXiv:2406.06768 (2024). [49] J. Xu, Y. Tian, P. Ma, D. Rus, S. Sueda, and W. Matusik. “Prediction-guided multi-objective reinforcement learning for continuous robot control”. In: International conference on machine learning. PMLR. 2020, pp. 10607–10616. [50] F. Yang, H. R. Zhang, S. Wu, C. Ré, and W. J. Su. “Precise high-dimensional asymptotics for quantifying heterogeneous transfers”. In: Journal of Machine Learning Research 26.113 (2025), pp. 1–88. [51] R. Yang, H. Xu, Y. Wu, and X. Wang. “Multi-task reinforcement learning with soft modularization”. In: Advances in Neural Information Processing Systems. Vol. 33. 2020, pp. 4767– 4777. [52] R. Yang, X. Sun, and K. Narasimhan. “A generalized algorithm for multi-objective reinforcement learning and policy adaptation”. In: NeurIPS 32 (2019). [53] T. Yang, S. Cen, Y. Wei, Y. Chen, and Y. Chi. “Federated natural policy gradient and actor critic methods for multi-task reinforcement learning”. In: Advances in Neural Information Processing Systems 37 (2024), pp. 121304–121375. [54] T. Yu, D. Quillen, Z. He, R. Julian, K. Hausman, C. Finn, and S. Levine. “Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning”. In: Conference on Robot Learning. 2020, pp. 1094–1100. [55] Z. Zhang, M. Duan, Y. Ye, and H. R. Zhang. “Scalable multi-objective and meta reinforcement learning via gradient estimation”. In: arXiv preprint arXiv:2511.12779 (2025). [56] Z. Zhang, M. Duan, and H. Zhang. “Efficient estimation of kernel surrogate models for task attribution”. In: International Conference on Learning Representations. 2026, pp. 61822– 61848.

14

A

Policy Gradient Estimation

In Algorithm 2, we compute the kernel by minimizing the following objective over the training set: min

gα ∈H

n X i=1

2 v(Si ) − gα (Si ) + λ∥gα ∥2Ψ ,

(5)

where λ > 0 is a regularization parameter and Ψ is an n × n kernel matrix with entries Ψi,j = ψ(Si , Sj ). Since
S is binary, consider the radial basis function (RBF) kernel: ψ(Si , Sj ) = exp − γ∥Si − Sj ∥2 . By the representer theorem of kernel methods, the minimizer is: gα (S) =

n X

αi ψ Si , S ,

i=1

where the coefficients α are obtained via (Ψ + λ Id)−1 V with V = [v(S1 ), . . . , v(Sn )]⊤ , and Id is the identity matrix. Below we describe how we obtain v(Si ). First-order approximation. We approximate the PPO surrogate objective (See Appendix C.3 for a detailed review of PPO) using a first-order Taylor expansion. Let φt = ∇θ log πθ (at |st )|θ=θ∗ be the gradient feature vector. The policy objective is approximated as: h i bt · (1 + φ⊤ ∆θ) , J(θ) ≈ Et A t bt is the advantage function. where ∆θ = θ − θ∗ and A Directly maximizing this linear approximation is unbounded. To obtain a robust estimator, we reformulate this optimization as a weighted binary classification problem. Intuitively, we seek an b update ∆θ that aligns the policy change φ⊤ t ∆θ with the sign of the advantage At . By defining a bt ) and a sample weight ηt = |A bt |, we maximize the margin yt φ⊤ binary label yt = sign(A t ∆θ. This is effectively approximated by minimizing the weighted logistic loss, which provides a bounded surrogate for the sign-agreement objective: X

1 ηt ·log 1 + exp −yt φ̃⊤ . v(Si ) := min LSj (θ∗ +∆θ) where LSj (θ∗ +∆θ) = t ∆θ ∆θ |DSi | t∈DSi

This formulation enables rapid estimation of the policy performance for any subset Si without full retraining. As shown in Table 6, the linearization error remains low (< 2%) within the trust region. Another challenge is the high dimensionality of gradient vectors. We address this by applying random Gaussian projections from φt to a low-dimensional space. By the Johnson–Lindenstrauss Lemma, this projection provably preserves the pairwise similarity between pairs of gradients. Solving the regression problem in the reduced space then takes only a few seconds. Table 6: We empirically find that the approximation error of ϵ is negligible for several interactive RL environments. We report the mean and standard deviation of the approximation error across 10 random subsets. We defer a detailed description of the setup to the experiments section. Distance

MT10

CartPole

Highway

Lunarlander

0.1% 0.5% 1.0%

0.01±0.01 % 0.43±0.73 % 0.32±0.56 %

0.12±0.14 % 0.73±0.10 % 0.98±0.65 %

0.02±0.02 % 0.11±0.09 % 2.04±0.58 %

0.06±0.01 % 0.03±0.02 % 0.48±0.01 %

Specifically, we compute the relative residual sum of squares (RSS) error across several RL environments: MT10 from MetaWorld [54], CartPole, LunarLander, and Highway from Gymnasium [41]. In each case, a four-layer MLP policy is trained, and gradients are estimated from 2,048 steps per task. The results are averaged over 10 randomly sampled subsets of size 5. As shown in Table 6, the RSS error remains below 2% when ∥θ − θ∗ ∥ is small with a proper initialization θ⋆ , indicating high accuracy in the linear approximation. The error gradually increases to around 10% for perturbations up to 5%. These results validate the surrogate model’s ability to approximate outcomes near the meta-policy. 15

Algorithm 3 Scalable Kernel Surrogate Estimation using Policy Gradient Estimation (P OLICYG RAD E X) Input: n subsets S1 , . . . , Sn of {1, . . . , m}; Initial meta-policy πθ⋆ Require: Number of episodes T ; Projection dimension d 1: πθ⋆ ← Set up the meta-policy for all objectives in {1, . . . , m} 1 2: P ← A p by d isotropic Gaussian random projection matrix with mean zero and variance d 3: for t = 1, . . . , T do 4: for i ∈ {1, . . . , m} do 5: φ ei,t ← P ⊤ ∇θ log πθ (ai,t | si,t )|θ=θ⋆ bi,t | 6: ηi,t ← |A bi,t ) 7: yi,t ← sign(A 8: end for 9: end for 10: for j = 1, . . . , n do (j) b S (θ⋆ + P ∆θd ) 11: ∆θbd ← arg min∆θd ∈Rd L j (j) (j) ⋆ 12: θb ← θ + P ∆θbd b S (θb(j) ) 13: vb(Sj ) ← −L j 14: end for 15: return v b(S1 ), . . . , vb(Sn ) Random projection. We now describe the implementation of the random projection step in our attribution procedure. We sample a random projection matrix P ∈ Rp×d , where d is smaller than p and every entry of P is independently drawn from a Gaussian distribution N (0, d−1 ). We project the high-dimensional gradients to a d-dimensional space as φ̃i,t = P ⊤ φi,t . Then, we solve a logistic regression problem in the d-dimensional space with θd ∈ Rd : X 1 θbd ← arg min ℓ(φ̃, y, w; θd ), θd ∈Rd |DSj |

(6)

(φ,y,w)∈DSj

for any j = 1, 2, . . . , m. Finally, we map the solution from dimension d back to the original dimension p as θb(j) = θ⋆ + P θbd .   p Based on the Johnson-Lindenstrauss lemma, when d = O log , for any φi with ∥φi ∥ ≤ G and 2 ϵ any θ, θ0 with ℓ2 -norm at most D, we have |⟨gi , θ − θ0 ⟩ − ⟨P gi , P (θ − θ0 )⟩| ≤ ϵ|⟨φi , θ − θ0 ⟩| ≤ 2GDϵ. This ensures that the random projection step will preserve the accuracy of the gradient estimation procedure. See Algorithm 3 for the complete description. Correlation between attribution scores and LOO analysis. The goal of this experiment is to evaluate whether an attribution method can predict which trajectory subsets are more useful for policy improvement. For each task, we first collect a fixed pool of trajectories and sample multiple trajectory subsets from that pool. Each subset is used under the same update protocol to estimate its true downstream effect on the policy. The resulting subset performance can be measured by hypervolume. Given these true subset effects, each attribution method assigns a predicted score to every subset. We then compare the ranking induced by the predicted scores with that induced by the true subset effects. The LDS score is the Spearman rank correlation between these two rankings. A higher LDS means the attribution method better identifies which trajectory subsets are actually more beneficial. In Figure 3, we illustrate the correlation between the kernel surrogate attribution scores and leaveone-out analysis results. The results show that these two are strongly correlated across different tests. 16

6 3 0 −3 −6

0.5 Γ

LOO (×10−4)

Correlation = 0.97

Correlation = −0.99

0.3 0.1

−6 −3 0 3 6 Attribution Result (×10−4)

−0.4 −0.2 0.0 Attribution Result

(a) Trajectory-level attribution.

(b) Objective-level attribution.

Figure 3: Correlation analysis of attribution scores against LOO scores (left) and objective conflict coefficient Γ (right). Remark A.1. We describe several natural extensions of our approach. First, our algorithms naturally extend to online multitask RL [55], where the state-action space varies across tasks. We leave further exploration of these benchmarks to future work. Second, kernel surrogates can also be used to measure the influence of an individual trajectory on the overall model behavior. This can be accomplished by sampling subsets of trajectories instead of objectives in the above algorithm. Lastly, while we primarily focus on probabilistic policies, similar ideas can be extended to deterministic policies. Remark A.2. Our problem formulation relates to multi-objective optimization in prior literature [34, 6], and we extend this line of work to the online learning setting. Further exploring the connection between ensemble learning and online boosting [5] is another direction for future work. Our work connects to the literature on influence estimation and mechanistic interpretability, which aims to trace model behavior back to influential training data. Prior work include influence functions [23], TracIn [35] and linear surrogate models [26]. In reinforcement learning, recent efforts have adapted these techniques to explain policy decisions, including trajectory-level attribution in offline RL [11] and snapshot influence functions for filtering harmful data in online RL [17]. One of the open questions in this area is to develop better theoretical characterizations of attribution methods. Our kernel-based objective attribution thus offers a principled approach and accurately estimates second-order interactions across preferences. This connection seems particularly relevant in light of recent advances in RL reasoning [4].

B

Complete Proofs

In this section, we present the proof of Theorem 3.6 in Appendix B.1. We introduce a lower bound in Appendix B.2 that matches the upper bound. Next, we analyze the magnitude of Γ in Algorithm B.3. Finally, in Appendix B.4, we present a relaxation when only an approximate low-rank basis assumption holds. B.1

Proof of Theorem 3.6

This section gives a complete proof of Theorem 3.6. The proof has four key steps. Lemma B.1 reduces cumulative regret to a sum of on-policy Bellman residuals. d¯h splits each residual into a conflict factor (the χ2 deviation of the deployed occupancy from d¯h ) and an in-sample factor (the squared Bellman residual measured under d¯h ). Lemma B.2 uses Γ, and Lemma B.3 uses the schedule regularity in Assumption √ 3.5. Lemma B.4 converts the witness-side error into the confidence radius β. Steps 3 and 4 give a T stable-phase rate, while the burn-in phase contributes O(Ht0 ) with t0 = O(Ccov Kβ). Notations. We analyze the pooled-confidence version of the routed optimistic algorithm. At the (t−1) beginning of episode t, each basis class Fk has a confidence set Fk (β) constructed from the pooled history D(t−1) = {(τ (i) , wi ) : i < t}, meaning that the regression residual is computed against every past trajectory, not only the trajectories routed to basis k. Routing determines which 17

optimistic basis is executed; the confidence guarantee used below controls the Bellman residual of the selected function relative to the cumulative occupancy across all previous episodes. After observing wt , the learner chooses (kt , f (t) ) ∈ arg

max (t−1) k∈[K], f ∈Fk (β)

V1f (s0 ; wt ), Vhf (s; w) := max fh (s, a; w). a

(7)

The deployed policy π (t) is greedy with respect to f (t) under wt , with state-action occupancy (t) (t) dh := dπh . Write the scalarized Bellman residual of the selected optimistic function as (t)

(t)

(t)

δh (s, a) = fh (s, a; wt ) − (Thwt fh+1 )(s, a), (t)

with the convention fH+1 ≡ 0. Finally, define the basis-mixture witness d¯h := K −1 Pt−1 (i) (t) the un-normalized cumulative empirical occupancy d¯ := d . i=1

h

⋆ πbk k=1 dh and

PK

h

2

Lastly, recall that the χ -divergence between two distributions P (x) and Q(x) is defined as χ2 (P ∥Q) =

X x:Q(x)>0

(P (x) − Q(x))2 . Q(x)

Proof structure. The proof relies on two events holding simultaneously, each with probability at least 1 − δ/2 (so that their intersection holds with probability at least 1 − δ). For Eopt , every ⋆ (t−1) realizable Qπbk (·; w) remains in its confidence set Fk (β) for all relevant t, k, w. This is the standard optimism event for confidence-set value iteration, union-bounded over the K basis classes. As for Ereg , for every selected f (t) , the cumulative squared Bellman residual on past trajectories is bounded by β. This is the standard in-sample regression event, again, union-bounded over the K basis classes. Next, we work on the intersection of Eopt and Ereg . Lemma B.1. On the event Eopt , for every episode t, V1f

(t)

⋆ (s0 ; wt ) ≥ J (πw ; wt ). t

⋆ Proof. Assumption 3.4 expresses the occupancy of πw as a convex combination of the basis occupancies. Since the scalarized value is linear in the occupancy measure, X ⋆ ⋆ J (πw ; w) = νw (k)J (πbk ; w). k

⋆

By Lemma 3.8, there exists k (wt ) ∈ [K] such that the optimal MORL policy and the optimal basis ⋆ ⋆ policy at index k ⋆ (wt ) have the same scalarized return: J (πw ; wt ) = J (πbk ⋆ (w ) ; wt ). t t ⋆

(t−1)

By event Eopt , the corresponding true Q-function Qπbk⋆ (wt ) (·; wt ) lies in Fk⋆ (wt ) (β). Restricting the joint argmax in (7) to k = k ⋆ (wt ) then yields V1f

(t)

(s0 ; wt ) ≥

π⋆ ⋆ bk (wt )

max (t−1)

f ∈Fk⋆ (w ) (β)

V1f (s0 ; wt ) ≥ V1Q

(s0 ; wt )

t

⋆ ⋆ = J (πbk ⋆ (w ) ; wt ) = J (πw ; wt ). t t

Lemma B.1 allows us to upper bound regret by the gap between the optimistic value and the value actually obtained by the greedy policy. The usual telescoping identity for finite-horizon Bellman residuals gives Reg(T ) ≤ =

T h X

V1f

t=1 T X H X

(t)

i (s0 ; wt ) − J (π (t) ; wt )

h i (t) E(s,a)∼d(t) δh (s, a) . h

t=1 h=1

18

(8)

The last equality follows from the standard layerwise telescoping along the trajectory of π (t) . Because (t) (t) π (t) is greedy with respect to f (t) , at each step h, Vhf (sh ; wt ) = fh (sh , ah ; wt ). Subtracting the (t)

scalarized reward plus the next optimistic value at each layer telescopes from V1f (s0 ; wt ) down to (t) the realized scalarized return, leaving exactly the expected sum of δh . h i (t) Let us analyze the term E(s,a)∼d(t) δh (s, a) in the regret upper bound in equation (8). For each t ph and h, multiply and divide by d¯h (s, a) inside the inner product: (t)

Ed(t) [δh ] = h

q q X d(t) (s, a) q  (t)  (t) (t) ph · d¯h (s, a)δh (s, a) ≤ ϕh (dh ) · Ed¯h (δh )2 . ¯ dh (s, a) s,a

(9)

Notably the conflicting factor ϕh (d) is connected with the χ2 -divergence: ϕh (d) :=

X d(s, a)2 = 1 + χ2 (d∥d¯h ). d¯h (s, a) s,a

The two factors in equation (9) are controlled separately: the conflict factor by Assumption 3.5 and the in-sample factor by combining the witness-comparison bound with the pooled-regression guarantee. Lemma B.2. Under Assumption 3.5, for every t and h, (t)

ϕh (dh ) :=

X d(t) (s, a)2 (t) h = 1 + χ2 (dh ∥d¯h ) ≤ 1 + Γ. d¯h (s, a) s,a

(t)

Proof. By Assumption 3.5, dh =

P

kν

(t)

π⋆

(k)dhbk . The map

d 7→ ϕh (d) =

X d(s, a)2 d¯h (s, a) s,a

is a squared norm in the measure weighted by d¯−1 h , hence convex. Jensen’s inequality gives X π⋆ (t) ϕh (dh ) ≤ ν (t) (k)ϕh (dhbk ) ≤ 1 + Γ, k

where the last step is Definition 3.3. Lemma B.3. Under Assumption 3.5 (with constants c0 ∈ (0, 1] and burn-in time t0 ∈ N), for every t ≥ t0 , h ∈ [H], and (s, a), c0 (t − 1) ¯ (t) d¯h (s, a) ≥ dh (s, a). Ccov Proof. The cumulative empirical occupancy can be expanded in terms of the basis occupancies: K K (t) ⋆ d¯h (s, a) X (t) c0 X πbk c0 ¯ π⋆ = ν (k)dhbk (s, a) ≥ dh (s, a) = dh (s, a). t−1 Ccov K Ccov k=1

k=1

The inequality is exactly the stable-phase lower bound in Assumption 3.5. Thus after burn-in, the data distribution accumulated by the algorithm pointwise dominates the uniform basis mixture up to the factor Ccov /c0 . Lemma B.4. On event Ereg , for every t ≥ t0 and h ∈ [H], h i Ccov β (t) Ed¯h (δh )2 ≤ . c0 (t − 1) 19

Proof. The standard regression guarantee for optimistic confidence sets, union bounded over k ∈ [K], gives for the selected f (t) (i.e., on the event Ereg ), t−1 X i=1

h i h i (t) (t) Ed(i) (δh )2 = Ed¯(t) (δh )2 ≤ β. h

(10)

h

This is exactly where the proof uses pooled confidence updates: the measure on the left is the cumulative occupancy across all previous episodes, not just those routed to kt . Lemma B.3 gives d¯h (s, a) ≤

Ccov ¯(t) d (s, a), for t ≥ t0 . c0 (t − 1) h (t)

Multiplying this pointwise inequality by (δh (s, a))2 and summing over (s, a), then applying (10), yields i h i h Ccov β Ccov (t) (t) Ed¯h (δh )2 ≤ Ed¯(t) (δh )2 ≤ . c0 (t − 1) h c0 (t − 1) Proof of Theorem 3.6. Combining equation (9) with Lemmas B.2 and B.4 gives, for every t ≥ t0 and h ∈ [H], s s √ C β Ccov (1 + Γ)β cov (t) Ed(t) [δh ] ≤ 1 + Γ · = . (11) h c0 (t − 1) c0 (t − 1) We split the regret (8) at the burn-in time t0 : Reg(T ) ≤

tX H 0 −1 X

V1f

(t)

h

t=1 h=1

T X H X

(t)

Ed(t) [δh ] . h

t=t0 h=1

{z

| During burn-in, for each t < t0 ,

(t)

Ed(t) [δh ] + }

(I)

|

{z

(II)

}

(t) (t) [δh ] = V1f (s0 ; wt ) − J (π (t) ; wt ) ≤ H since both h Ed(t) h

P

∈ [0, H] and J (π (t) ; wt ) ∈ [0, H]. Hence (I) ≤ H t0 .

During the stable phase, substituting (11) and summing over h and t, II is at most s s s T T X Ccov (1 + Γ) β Ccov (1 + Γ) β X Ccov (1 + Γ) β T 1 √ H =H ≤ 2H , c0 (t − 1) c0 c0 t−1 t=t t=t 0

using

PT

t=t0 (t − 1)

0

−1/2

≤

√ −1/2 ≤ 2 T. u=1 u

PT −1

Adding (I) and (II) and absorbing the universal constant 1/c0 into O(·), s  p  Ccov (1 + Γ)βT Reg(T ) ≤ Ht0 + 2H = O H Ccov (1 + Γ)βT + O(Ht0 ). c0 The preference process satisfies the schedule regularity of Assumption 3.5 after t0 = O(Ccov Kβ) episodes (a standard Hoeffding’s bound on the visitation counts of the K basis components, with the log factor absorbed into β). Substituting yields   p Reg(T ) ≤ O H Ccov (1 + Γ)βT + HCcov Kβ , which is equation (2). The corresponding worst-case scaling follows by applying 1 + Γ ≤ K from Lemma B.5. For completeness, we record the structural lemma used above; it shows that the conflict coefficient is at most K − 1 for any basis, with equality (up to lower-order terms) in the disjoint regime that powers the lower bound. 20

π⋆

Lemma B.5. For any collection of K basis occupancies {dhbk }k∈[K] and every h ∈ [H],  ⋆  π Γ = max max χ2 dhbk d¯h ≤ K − 1. h∈[H] k∈[K]

Equality holds (up to lower-order terms) when the basis occupancies have pairwise disjoint supports. ⋆

⋆

π 1 πbk Proof. Fix h and k. Pointwise, d¯h (s, a) ≥ K dh (s, a) on the support of dhbk . Hence

χ

2



π⋆ dhbk

⋆ ⋆  X (dπbk 2 X (dπbk (s, a))2 h h (s, a)) ¯ − 1 = K − 1. −1≤ dh = ⋆ πbk d¯h (s, a) (s, a) s,a (1/K) d s,a

h

π⋆

1 The disjoint-support case attains equality because then d¯h (s, a) = K dhbk (s, a) on the support.

B.2

Proof of the regret lower bound

Theorem B.6. There exists a family of MOMDPs with K basis policies, Ccov ≤ K, and Γ = K − 1, such that for any (possibly randomized) learning algorithm A and any T ≥ K, a preference sequence that cycles uniformly through {e1 , . . . , eK } satisfies  √   p    E Reg(T ) ≥ Ω H KT = Ω H (1 + Γ)T . Together, Theorems 3.6 and B.6 pin down the dependence on K and Γ up to factors of

p

Ccov log |F|.

In the following proof, we prove the lower bound by embedding a standard Bernoulli two-armed bandit problem into a simple subclass of MOMDPs. This is sufficient because a lower bound for one valid MOMDP family is automatically a lower bound for the larger MOMDP class. The constructed family has K pairwise-disjoint sub-chains, one per objective, each containing one Bernoulli twoarmed bandit. Here, a sub-chain means a branch of the environment state space, not a policy: the k-th optimal basis policy is the policy that routes into sub-chain Sk and then plays the better binary action. Under a cyclic preference sequence, regret has two sources: 1) a routing term for episodes whose first action does not match the active preference; 2) K independent bandit terms for wrong binary choices inside correctly routed sub-chains. We then show that for each preference ek , the learner faces a two-armed bandit on the episodes with active preference ek , with mis-routing acting as a no-information mistake that also costs order ∆. The horizon does not create a harder statistical problem in this construction: after the binary decision, the remaining states reveal no additional choices or independent samples. Instead, the same Bernoulli outcome is paid over the remaining H − 1. p H − 1 stages, so the bandit regret is simply multiplied by√ Tuning the bandit gap to ∆ = 18 K/T makes the total unavoidable cost scale as ∆T = Θ( KT ), √ and the repeated payoff yields the claimed Ω(H KT ) lower bound. Hard MOMDP instances. Fix K ≥ 2, H ≥ 2, and ∆ ∈ (0, 1/4]. The MOMDP has m = K objectives and a single start state s0 . From s0 , the K deterministic actions a ∈ [K] route the agent to disjoint state-space branches S1 , . . . , SK , which we call sub-chains. Inside sub-chain Sk , the agent makes one binary decision u ∈ {0, 1} at the second step; thereafter, the chain is uninformative. There is an unknown bit bk ∈ {0, 1}, and the k-th reward coordinate at every step inside Sk equals a single Bernoulli outcome drawn at the moment of the binary decision, with mean 1 2 +∆

if u = bk , 12

if u ̸= bk .

All other reward coordinates are zero. Thus, each episode yields only one statistically informative bandit observation, even though it has a horizon of H. A correctly routed episode where the wrong binary action is chosen contributes regret (H − 1)∆, and an incorrectly routed episode contributes regret at least (H − 1)∆ as well. Preference sequences. The preference sequence cycles through e1 , e2 , . . . , eK , e1 , e2 , . . ., so each ⋆ preference ek appears between ⌊T /K⌋ and ⌈T /K⌉ times. The optimal basis policy πbk routes to sub-chain Sk and plays bk ; the K basis occupancies are supported on disjoint sub-chains, so by Lemma B.5, Γ = K − 1, and the basis-mixture witness d¯h gives Ccov ≤ K. We use a lower bound result from the work of Lattimore and Szepesvári [25]. 21

Lemma B.7 (Bandit lower bound [25]). For any randomized algorithm interacting with a Bernoulli two-armed bandit of gap ∆ ∈ (0, 1/4], the expected cumulative regret after n pulls is at least cLB min(∆n, 1/∆) for a universal constant cLB > 0, in the worst case over the unknown optimal arm. Proof of Theorem B.6. We proceed in three steps. First, for a fixed interaction history, partition the T episodes into two disjoint sets: M episodes where the learner mis-routes, meaning that its first action does not equal the index kt of the active preference ekt . Each such episode loses at least (H − 1)∆ relative to the optimal policy for ekt . For each k ∈ [K], nk episodes where the learner correctly routes to Sk under preference ek . Conditional on these episodes, the learner observes exactly nk pulls from the two-armed Bernoulli bandit associated with unknown bit bk . Let Mk be the number of mis-routed episodes whose active preference is ek , and let mk := Mk + nk be the total number of appearances of preference ek . The cyclic sequence fixes mk deterministically, PK PK with ⌊T /K⌋ ≤ mk ≤ ⌈T /K⌉, and M + k=1 nk = k=1 mk = T pathwise. Taking expectation over the learner’s randomness and the bandit rewards, the cumulative regret satisfies E[Reg(T )] ≥ (H − 1)∆ E[M ] + (H − 1)

K X

(nk )], E[Regbandit k

(12)

k=1

where Regbandit (nk ) denotes the cumulative regret of the induced bandit on sub-chain Sk (the leading k H − 1 factor accounts for the fact that each Bernoulli outcome is paid out over H − 1 steps). p Next, set ∆ = 18 K/T , which satisfies ∆ ≤ 1/8 since T ≥ K. The cyclic preference sequence ensures mk ≤ ⌈T /K⌉ ≤ 2T /K, so p p 1 1 T /K ≤ ∆ . ∆mk ≤ 81 K/T · 2T K = 4 For a fixed k, restrict attention to the mk episodes whose active preference is ek . In these episodes, the learner must either route to Sk and choose one of the two bandit arms, or mis-route and incur one-stage scalarized regret at least ∆ while receiving no observation from the k-th bandit. Thus, the sum ∆Mk + Regbandit (nk ) is lower bounded by the regret of a Bernoulli two-armed bandit problem k with mk opportunities. Lemma B.7 gives h i E ∆Mk + Regbandit (nk ) ≥ cLB min(∆mk , 1/∆) = cLB ∆mk . k Summing over k yields ∆E[M ] +

K X k=1

E[Regbandit (nk )] ≥ cLB ∆ k

K X

mk = cLB ∆T.

k=1

Lastly, substituting the preceding bound into equation (12), E[Reg(T )] ≥ cLB (H − 1)∆T, p 1 Substituting ∆ = 8 K/T , we have  √  √ cLB (H − 1) KT = Ω H KT . E[Reg(T )] ≥ 8 p Since the construction has Γ = K − 1, this is equivalent to Ω(H (1 + Γ)T ). Thus, we have completed the proof of the lower bound. B.3

Bounds on objective conflict coefficients

Although Algorithm 1 does not require Γ as an input, its off-policy transfer step is governed by the same overlap quantity. At iteration t, sampling a basis policy uniformly yields the routed-ensemble mixture and its associated conflict measure  (t−1)  K 1 X πj(t−1) (t) πj 2 ¯RE . d¯RE = d , Γ = max max χ d d (13) h,t h,t RE h K j=1 h h∈[H] j∈[K] (t)

When the learned ensemble recovers the latent basis policies, ΓRE coincides with Γ. The following proposition formalizes that the off-policy estimators used to route and update the ensemble have (t) variance inflated by exactly the factor 1 + ΓRE . 22

Proposition B.8. Fix an iteration t of Algorithm 1, a stage h, and a target basis index j ∈ [K]. Suppose B replay samples (si , ai ) are drawn i.i.d. from d¯RE h,t , and let gh : S × A → [−G, G] be any bounded measurable signal with target value θj,h = E π(t−1) [gh (s, a)]. dh j

The importance-weighted off-policy estimator B

π

(t−1)

(si , ai ) 1 X dhj θbj,h := gh (si , ai ) B i=1 d¯RE (s h,t i , ai ) is unbiased and satisfies i G2 1 + Γ(t)
h RE 2 b . E (θj,h − θj,h ) ≤ B (t−1) (t) ⋆ In the idealized case πj = πbj for all j, ΓRE = Γ.

(14)

π

(t−1)

Proof. Fix iteration t, stage h, and target basis index j. For brevity, write dj := dhj

, µ := d¯RE h,t ,

(t)

and ρj (s, a) := dj (s, a)/µ(s, a). Finite ΓRE implies dj ≪ µ, soP ρj is well P defined on supp(µ). Since dj and µ are probability distributions over S × A at stage h, s,a dj = s,a µ = 1. Each replay sample (si , ai ) is drawn from µ, so X X dj (s, a) E[ρj (si , ai )gh (si , ai )] = µ(s, a) gh (s, a) = dj (s, a)gh (s, a) = θj,h . µ(s, a) s,a s,a Averaging over B samples preserves the mean: E[θbj,h ] = θj,h . For a single sample, the second moment of the importance-weighted signal is bounded by X dj (s, a)2
  (t)
= G2 1 + χ2 (dj ∥µ) ≤ G2 1 + ΓRE , (15) Eµ ρj (s, a)2 gh (s, a)2 ≤ G2 µ(s, a) s,a P where the equality uses the standard χ2 -identity s,a d2j /µ = 1 + χ2 (dj ∥µ) (which holds because (t)

dj and µ are probability distributions), and the last inequality is the definition of ΓRE . The B samples are independent, so   (t)
h i Eµ ρ2j gh2 G2 1 + ΓRE 2 b b ≤ , E (θj,h − θj,h ) = Var(θj,h ) ≤ B B (t−1) (t) ⋆ which leads to equation (14). If πj = πbj for every j ∈ [K], then µ = d¯h and ΓRE = Γ by Definition 3.3. B.4

Approximate low-rank conditions

Next, we show how the regret bound changes when Assumption 3.4 only holds approximately. We separate two effects. Relative to the best policy in the chosen K-policy basis, the proof of Theorem 3.6 still gives a sublinear regret bound, with the conflict factor inflated by ε. If the chosen basis does not contain a truly optimal policy for a preference, then true regret also includes the gap between the true optimum and the best basis policy. PK π⋆ Let d¯h = K −1 k=1 dhbk be the same basis-mixture witness used in the proof of Theorem 3.6. We replace Assumption 3.4 by the following approximate version. ⋆ ⋆ Assumption B.9. There exist latent basis policies {πb1 , . . . , πbK } and a tolerance ε ≥ 0 such that (t) every deployed policy π ∈ {π : t ≤ T } admits a single mixing vector νπ ∈ ∆K−1 satisfying, for every stage h ∈ [H], dπh = qπ,h + eπ,h , qπ,h :=

K X

k=1

π⋆

νπ (k)dhbk , ∥eπ,h ∥2d¯−1 := h

X eπ,h (s, a)2 ≤ ε2 . d¯h (s, a) s,a

The norm is interpreted with the usual support convention: finite norm requires eπ,h (s, a) = 0 whenever d¯h (s, a) = 0. 23

The d¯−1 norm is chosen to match the Cauchy–Schwarz step in Theorem 3.6: the proof h -weightedP controls ϕh (d) = s,a d(s, a)2 /d¯h (s, a) = ∥d∥2d¯−1 . Thus, an error bound in this same norm can be h carried through the original argument by the triangle inequality. For this approximate statement, we keep the stable-coverage consequence of Assumption 3.5: for all t ≥ t0 , h ∈ [H], and (s, a), (t) d¯h (s, a) :=

t−1 X c0 (t − 1) ¯ (i) dh (s, a) ≥ dh (s, a). Ccov i=1

(16)

This is the only property of coverage needed for the pooled-regression step. It can be assumed directly or derived from an approximate exploration condition that guarantees the accumulated actual occupancies dominate the basis mixture. For a preference w, define the best value achievable by the chosen basis as ⋆ JK⋆ (w) := max J (πbk ; w) = max

ν∈∆K−1

k∈[K]

K X

⋆ ν(k)J (πbk ; w).

k=1

The equality holds because the objective is linear in the mixing weights. We measure basis-relative regret by T h i X RegK (T ) := JK⋆ (wt ) − J (π (t) ; wt ) . t=1

Proposition B.10. Suppose scalarized rewards are bounded in [0, 1] per step, Bellman realizability and completeness hold for each per-basis class Fk , Assumption B.9 holds with tolerance ε, and the stable-coverage condition (16) holds after a burn-in time t0 = O(Ccov Kβ), where β := c1 log(K|F |T /δ). Then, with probability at least 1 − δ, the pooled-confidence routed-ensemble algorithm satisfies  p  √
RegK (T ) ≤ O H Ccov βT 1 + Γ + ε + HCcov Kβ . (17) When ε = 0 and the basis is exact, RegK (T ) = Reg(T ) and this reduces to Theorem 3.6. Proof. The proof follows the same sketch as Theorem 3.6 (Appendix B.1), with two simplifications ⋆ and one change. First, the comparator is changed from the true optimal value J (πw ; w) to the basis⋆ oracle value JK (w), so routed optimism becomes exact against this weaker comparator (Lemma B.11 q √ √ (t) below). Second, the conflict factor ϕh (dh ) inflates from 1 + Γ (Lemma B.2) to 1 + Γ + ε (Lemma B.12 below), because deployed occupancies are only approximately in the basis hull. Third, the witness-comparison and pooled-regression steps are unchanged: they use only the stable coverage condition (16) and Bellman completeness, neither of which is affected by relaxing Assumption 3.4. We carry out the modifications below. First, we show the following claim on the optimism of the routed basis. Claim B.11. On the optimism event Eopt (defined in Appendix B.1), for every episode t, V1f

(t)

(s0 ; wt ) ≥ JK⋆ (wt ).

⋆ ⋆ Proof. Let kK (wt ) ∈ arg maxk∈[K] J (πbk ; wt ). By the optimism event Eopt , the true Q-function π⋆ ⋆

(t−1)

Q bkK (wt ) (·; wt ) belongs to the confidence set Fk⋆ (wt ) (β). The routed optimistic choice in equation K (7) maximizes over all basis indices and all functions in their confidence sets, so we may restrict the π⋆ ⋆ ⋆ maximization to the single feasible candidate (kK (wt ), Q bkK (wt ) ). This gives (t) V1f (s0 ; wt )

π⋆ ⋆

≥

bk (wt ) K V1Q (s0 ; wt )

24

⋆ ⋆ = J (πbk ⋆ (w ) ; wt ) = JK (wt ). t K

Second, we demonstrate regret reduction via a certain identity. This step is identical to the regret reduction in equation (8). Working on the intersection Eopt ∩ Ereg (probability at least 1 − δ), Lemma B.11 together with the standard layerwise telescoping identity gives RegK (T ) ≤

T h X t=1

V1f

(t)

T X H i h i X (t) (s0 ; wt ) − J (π (t) ; wt ) = Ed(t) δh .

(18)

h

t=1 h=1

Below, we control the Bellman residual term on the right-hand side. Identical to equation (9), for every t ∈ [T ] and h ∈ [H], we have r h i q i h (t) (t) (t) Ed(t) δh ≤ ϕh (dh ) · Ed¯h (δh )2 .

(19)

h

Next, we show the following approximate conflict bound, which is the only step affected by ε. Claim B.12. Every policy π satisfying the decomposition in Assumption B.9 also satisfies, for every h ∈ [H], q √ ϕh (dπh ) ≤ 1 + Γ + ε. (20) Proof. Since ϕh (d) = ∥d∥2d¯−1 , Assumption B.9 and the triangle inequality in ℓ2 norm give h

q

ϕh (dπh ) = ∥qπ,h + eπ,h ∥d¯−1 ≤ ∥qπ,h ∥d¯−1 + ∥eπ,h ∥d¯−1 ≤ h

h

h

q

ϕh (qπ,h ) + ε.

The first summand is controlled exactly as in Lemma B.2: by convexity of ϕh and Definition 3.3, P  X ⋆ πbk π⋆ ϕh (qπ,h ) = ϕh ν (k) d ≤ νπ (k) ϕh (dhbk ) ≤ 1 + Γ. π k h k

Combining this display with the triangle-inequality bound proves equation (20). Lemma B.12 to the deployed policy π (t) yields q √ (t) ϕh (dh ) ≤ 1 + Γ + ε.

Applying

(21)

The cumulative-occupancy lower bound in equation (16), combined with the pooled-regression event Ereg , gives the same in-sample-to-witness bound as Lemma B.4: for every t ≥ t0 and h ∈ [H], s r h i Ccov β (t) 2 Ed¯h (δh ) ≤ . (22) c0 (t − 1) This step depends only on equation (16), the pooled-regression event Ereg , and Bellman completeness. It does not use exact basis decomposition. Finally, combining equations (19), (21), and (22), for every t ≥ t0 and h ∈ [H], s h i √
Ccov β (t) Ed(t) δh ≤ 1+Γ+ε . h c0 (t − 1)

(23)

We split the regret in equation (18) at the burn-in time t0 and bound each part. (t) P (t) For each t < t0 , h Ed(t) [δh ] = V1f (s0 ; wt ) − J (π (t) ; wt ) ≤ H, since both quantities lie in h [0, H]. Hence, the burn-in contribution is at most H t0 . √ PT PT −1 Substituting equation (23) and using t=t0 (t − 1)−1/2 ≤ u=1 u−1/2 ≤ 2 T , r r T X H T h i X √ √
Ccov β X
Ccov β T 1 (t) √ Ed(t) δh ≤ H 1 + Γ + ε ≤ 2H 1 + Γ + ε . h c0 t=t c0 t−1 t=t 0 h=1

0

25

Combined together, substituting t0 = O(Ccov Kβ), and treating t0 as a fixed constant yields   p √
1 + Γ + ε + HCcov Kβ , RegK (T ) ≤ O H Ccov βT · which leads to equation (17). Lastly, we connect basis-relative regret RegK (T ) to the cumulative regret Reg(T ) against the true ⋆ ⋆ optimal policy via a clean two-term decomposition. For a fixed basis {πb1 , . . . , πbK }, define the cumulative basis-approximation error along the realized preference sequence as T X   ⋆ J (πw ; wt ) − JK⋆ (wt ) . t

AK (T ) =

t=1

⋆ Since every basis policy is feasible, JK⋆ (wt ) ≤ J (πw ; wt ) for every t, so AK (T ) ≥ 0. The quantity t ⋆ AK (T ) depends on the basis {πbk } and the preference distribution P, but not on the algorithm.

First, we present the exact decomposition of regret relative to the true optimal policy. By telescoping the comparator JK⋆ (wt ) in and out of the regret sum, Reg(T ) =

T T h i X   X ⋆ ⋆ ⋆ (t) J (πw ; w ) − J (w ) + J (w ) − J (π ; w ) . t t t t K K t t=1

(24)

t=1

|

{z

}

AK (T )

|

{z

RegK (T )

}

Proposition B.10 controls the second term; the first depends only on the chosen basis. Second, we bound AK (T ) when optimal policies are also approximately in the hull. Following Assumption B.9, π⋆ we have dhw = qw,h + ew,h . Since scalarized rewards rhw (s, a) are bounded in [0, 1], its inner product with approximation error ew,h has q ⟨ew,h , rhw ⟩ ≤ ⟨ew,h , rhw ⟩ ≤ ∥ew,h ∥d¯−1 Ed¯h [(rhw )2 ] ≤ ε. h

Using the same mixing vector νw at every stage, ⋆ J (πw ; w) =

=

H X h=1 K X k=1

π⋆

⟨dhw , rhw ⟩ ≤

H X

⟨qw,h , rhw ⟩ + Hε

h=1

⋆ νw (k)J (πbk ; w) + Hε ≤ JK⋆ (w) + Hε.

Summing over t ∈ [T ] yields AK (T ) ≤ HεT. Lastly, combining equation (24) with the above, and Proposition B.10, we have   p √
Reg(T ) ≤ O HεT + H Ccov βT · 1 + Γ + ε + HCcov Kβ .

C

Omitted Experiments and Implementation Details

In this section, we describe several omitted experimental results as well as the implementation details that are left out from Section 4. We conduct the MO-Gymnasium experiments on an AMD Ryzen 7 9700X CPU, with a total training time of approximately 72 hours. Meta-World and RLHF experiments are performed on a server with an Intel Xeon E5-2623 v3 CPU and NVIDIA RTX A6000 GPUs. The Meta-World training takes 12 hours, and the RLHF experiment takes 1 hour. Next, we define the performance metrics used in our experiments. We compute Γ based on the χ2 divergence between the state occupancy distributions of single-objective basis policies. To account for the temporal diffusion effect described above, we use the time-averaged state occupancy H X (d¯πk (s) − d¯avg (s))2 1 X d¯π (s) = P (st = s), then Γ = max , k H t=0 d¯avg (s) s∈S

26

Table 7: Hyper-parameters for the routed ensemble procedure used in Algorithm 1. Parameter

Meta-World

MO-Gymnasium

Number of basis policies Base optimizer SAC buffer size Learning rate (Actor) Learning rate (Critic) Discount factor Batch size Network architecture

3 Adam 106 3 × 10−4 3 × 10−4 0.99 1280 MLP 256 × 256

3 Adam 106 3 × 10−4 3 × 10−4 0.99 256 MLP 256 × 256

where πk is the policy trained on objective k alone, and d¯avg is the uniform mixture of all basis occupancies. We train a kernel ridge regression model fˆ on the dataset of {(mi , yi )}. The attribution of a conflicting objective j (where j ∈ {5, . . . , 9}) is calculated as the predicted marginal gain fˆ(mtarget ∪ {j}) − fˆ(mtarget ), where mtarget is the mask containing only the target objective. Lastly, we provide the detailed hyperparameter settings used in our experiments to ensure reproducibility. Table 7 lists the parameters for the routed ensemble algorithm across different benchmarks. For routed ensemble, we adapt the base policy-learning algorithm for each environment. We use Soft Modularization [51] for Meta-World, Q-Pensieve [18] for continuous MO-Gymnasium tasks, and PQL [42] for discrete MO-Gymnasium tasks. For all baselines, we use the hyperparameters from their official implementations/repositories to ensure a fair comparison. Each baseline is trained for 5 × 105 time steps on continuous benchmarks and 104 time steps on discrete benchmarks. We implement kernel-based objective attribution in Algorithm 2 using a RBF kernel defined as ψ(Si , Sj ) = exp(−γ∥Si −Sj ∥2 ). We determine the kernel bandwidth γ = 0.1 and the regularization coefficient λ = 0.1 via cross-validation on the validation set. C.1

Synthetic environments

Multi-objective environments. We utilize a 2D parametric optimization environment. The policy is parameterized by a coordinate vector θ ∈ R2 . The agent aims to maximize a scalarized return J(θ, w) = w · r1 (θ) + (1 − w) · r2 (θ), where w ∈ [0, 1] represents the preference weight. We optimize θ using the Adam optimizer across a sweep of discrete weights w. All environments include a small regularization penalty −0.1∥θ∥22 . We define three distinct regimes: Case 1 (Aligned objectives). The reward functions are quadratic penalties centered at proximal locations µ1 = (1, 1) and µ2 = (1.2, 1.2). This configuration simulates tasks where improving one objective implicitly benefits the other. Case 2 (Conflicting objectives with a linear frontier). We construct a non-convex reward landscape to induce a disjoint set of optimal policies. The targets are separated at µ1 = (−2, 0) and µ2 = (2, 0). Crucially, we introduce a Gaussian barrier penalty P (θ) = −10 exp(−θx2 ) centered at the origin. This barrier prevents the optimization from settling in the intermediate region. Consequently, the optimal deterministic policies collapse to the extreme corners, and the Pareto frontier is formed by the linear convex hull of these solutions. Case 3 (Conflicting objectives with a concave frontier). We remove the central barrier while maintaining the separated targets µ1 = (−2, 0) and µ2 = (2, 0). The reward functions are standard negative Euclidean distances. This convex landscape allows for smooth interpolation between objectives. It results in a strictly concave Pareto frontier, in which intermediate policies outperform the linear combination of the corner solutions. Nonlinear synergy. We introduce an environment for conducting synthetic experiments to demonstrate synergy effects. This environment creates a synergy trap in which two objectives are individually detrimental or neutral but highly beneficial when combined. 27

We define a 2D parametric optimization task with M = 12 distinct objectives, indexed by j ∈ {0, 1, . . . , M − 1}. The objectives are arranged equidistantly on a unit circle (a clock face). The goal vector for the j-th objective, vj ∈ R2 , is defined by the angle ϕj = π2 − j · 2π M: vj = [cos(ϕj ), sin(ϕj )]⊤ . Here, objective 0 (north) is the designated target with vtarget = [0, 1]⊤ . The environment employs a specialized reward function R(a, S) for an action a ∈ R2 given a subset of active objectives S ⊆ {0, . . . , M − 1}, represented by a binary mask m ∈ {0, 1}M . The reward consists of a standard linear component and a nonlinear synergy component:   X R(a, S) = a⊤  vj  + I3∈S∧9∈S · κsyn · (a⊤ vtarget ), j∈S

where κsyn = 5.0 is the synergy bonus coefficient. The agent is modeled as a stochastic policy πθ (a) = N (µθ , Σ), where µθ = tanh(θ) and Σ = σ 2 I (with σ = 0.2). The parameter θ ∈ R2 is optimized via policy gradient, which optimizes the parameters of a stochastic policy by maximizing expected reward through Monte Carlo sampling, using the Adam optimizer with a learning rate of 0.1 for a horizon of Tep = 60 steps. A tabular environment on a grid. To validate the theoretical interactions between the objective conflict coefficient Γ and the coverability coefficient Ccov , we implement a controlled tabular environment. This setup allows for the exact calculation of occupancy measures and χ2 -divergences, avoiding the approximation errors inherent in deep RL settings. We consider a MOMDP modeled as an N × N grid (default N = 5), defined by the tuple M = (S, A, P r, r, γ). Consistent with the conflicting-objectives regime, we construct m objectives based on spatial navigation to distinct goal coordinates. Let G = {g1 , . . . , gm } ⊂ S be a set of diverse goal states. The vector-valued reward function r(s, a) ∈ Rm is defined using the negative Manhattan distance (ℓ1 norm): rk (s, a) = −∥coord(s′ ) − coord(gk )∥1 , where s′ is the next state and coord(·) maps a state index to its (x, y) grid position. We compute optimal policies exactly via soft value iteration. For a given preference weight w ∈ ∗ ∆m−1 , the scalarized reward is rw = ⟨w, r⟩. The policy πw is derived from the soft Bellman operator:     X Q(s, a) Q(s, a) V (s) = τ log exp , π(a|s) ∝ exp , τ τ a with temperature τ = 0.5. The exact state-action occupancy distribution dπ ∈ R|S||A| is computed by solving the linear system: dπ = (I − γPπ )−1 d0 , where Pπ is the policy-induced transition matrix and d0 is the uniform initial distribution. We explicitly calculate the conflict coefficient. We define the target mixture distribution d¯ as the uniform average of the occupancies of the single-objective experts: ¯ a) = 1 d(s, m

m X

⋆

dπk (s, a).

k=1

2

The conflict coefficient is then measured as the χ -divergence between a candidate policy’s occupancy and this target mixture: ¯ = Γ(π) = χ2 (dπ ∥d)

X (dπ (s, a) − d(s, ¯ a))2 . ¯ a) + ϵ d(s, s,a

We utilize this metric to compare coverability in Section 4.3. We find that a single scalarized policy πsingle exhibits a high χ2 -divergence, indicating poor coverage of the Pareto frontier. In contrast, a routed ensemble with K basis policies significantly reduces this divergence. 28

C.2

Additional empirical results

Empirical evaluation of the basis assumption. We measure the residual ϵ obtained by approximating preference-policy occupancies with convex combinations of basis-policy occupancies. Tabular occupancies are computed exactly, while benchmark occupancies are estimated from visitation distributions. Table 8 reports the mean and maximum residuals over the evaluated preferences. Table 8: Convex-hull occupancy residuals for exact tabular occupancies and empirical benchmark visitation distributions. Mean and maximum residuals are computed over the evaluated preferences. Setting

Basis construction

Tabular, aligned Tabular, linear Tabular, concave Tabular, concave MO-Hopper MO-Hopper MO-Hopper Deep-Sea-Treasure Fruit-Tree GridWorld, 21 distinct optima

Number of policies

Exact Exact Exact Exact Candidate-selected Candidate-selected Learned by Alg. 1 Learned by Alg. 1 Oracle Restricted learner

1 2 3 21 3 15 3 6 6 2

Mean ϵ −18

∼ 10 ∼ 10−9 0.186 1.45 × 10−4 0.443 0.231 1.33 0.15 0.553 0.475

Max ϵ ∼ 10−17 ∼ 10−8 0.55 6.10 × 10−4 0.80 0.51 1.42 0.75 0.85 3.474

In the concave tabular setting, the mean residual decreases from 0.186 at three bases to 0.088, 0.024, and 1.45 × 10−4 at five, nine, and 21 bases, respectively. On MO-Hopper, increasing the candidateselected basis from three to 15 policies decreases the mean residual from 0.443 to 0.231, whereas the three policies learned by Algorithm 1 have mean residual 1.33. These measurements show that a larger candidate basis can approximate the evaluated occupancies more closely, but the learned ensemble need not recover the exact structure assumed in the analysis. Severe basis under-specification. In a controlled GridWorld with 21 distinct preference-optimal policies, we restrict the learner to two policies for 3000 episodes. The resulting mean and maximum occupancy residuals are 0.475 and 3.474, and the cumulative value excess is 2780.4. This test measures performance when the available ensemble is substantially smaller than the set of preferenceoptimal policies. Comparison on RLHF tasks. We evaluate the extension of our approach to RLHF settings on synthetic data, HelpSteer2 [43], and UltraFeedback [10]. For the synthetic experiment, we construct a synthetic preference dataset that captures the helpfulness-safety trade-off in RLHF. Each prompt is paired with candidate textual responses corresponding to different response styles, while rewards are generated from a controlled two-objective preference function. This allows us to study expert routing under interpretable language scenarios while retaining access to an oracle policy. For the real-data experiments, we evaluate Qwen3-1.7B and Llama-3.2-1B on both HelpSteer2 and UltraFeedback, yielding four model–dataset configurations. All four configurations follow the same training protocol, with per-basis LoRA adapters trained using PPO. Table 9: Summary of trajectory attribution results on two MO-Gymnasium benchmarks, Deep Sea Treasure and Fruit Tree. Influence functions Linear surrogate models TracIn Algorithm 2

Deep Sea Treasure 0.28±0.51 0.62±0.39 0.70±0.40 0.75±0.14

Fruit Tree 0.30±0.57 0.71±0.53 0.75±0.45 0.81±0.18

Choice of N . Finally, we present comparison results by varying the size of the ensemble policy. In Figure 4, we illustrate the choice of N on the three datasets, including MO-HalfCheetah2d, MO-Hopper, and MO-Ant environments. 29

HV(×107)

HV(×106)

5.1 4.8

2

3

4

1.8 1.6

5

HV(×107)

2.0

5.4

2

3

N

4

5

2.2 2.0 1.8

N

2 3 4 5 6 7 N

Figure 4: Ablation analysis of the choice of the ensemble size N , measured by hypervolume (HV). C.3

Proximal policy optimization

In proximal policy optimization (PPO), access to the exact Aπ is not available. Instead, one must use bt computed from rollout trajectories and a learned value function Vϕ . A an advantage estimator A common choice is generalized advantage estimation (GAE), where the temporal-difference residual at time t is δt = rt + γVϕ (st+1 ) − Vϕ (st ), and the advantage estimate is L−1 X bt = A (γλ)l δt+l , l=0

for some truncation horizon L, the discount factor γ ∈ [0, 1), and GAE parameter λ ∈ [0, 1]. More bt to denote any scalar advantage estimate derived from the rollout and a baseline; generally, we use A bt as given and is independent of the particular estimator. our theory treats these A Training proceeds in rounds k = 0, 1, 2, . . .. In round k, the current policy πθ(k) interacts with the (k) k environment and collects a rollout buffer B (k) = {zi }ni=1 , where each record (k)

zi

bi ) = (si , ai , ri , log πθ(k) (ai | si ), vi , A

contains the transition (si , ai , ri ) together with auxiliary quantities such as the log-probability under bi . These records are the current policy, a discounted value estimate vi , and an advantage estimate A the atomic units used in PPO updates and form the basic entities for local attribution. Given a buffer B (k) , PPO performs a number of gradient steps to update θ from θ(k) to θ(k+1) by maximizing a clipped surrogate objective. For a single record z = (s, a, r, . . .), let ℓPPO (θ; z) denote the per-record loss corresponding to the standard clipped PPO objective (possibly combined with value and entropy terms). The empirical PPO loss over the buffer is then n

L̂(k) (θ) =

k 1 X (k) ℓPPO (θ; zi ), nk i=1

and PPO updates θ to approximately minimize L̂(k) (θ), starting from θ(k) .

30

Related documents

• Multi-Objective Reinforcement Learning Using Routed Ensembles and Trajectory Attribution#1459256
• LEMUR: Learning to Align with Multi-Objective Reinforcement Learning from Preference Feedback#422286
• End-to-End Safe Social Navigation via Multi-Task Reinforcement Learning and Probabilistic Perception#1393821
• End-to-End Safe Social Navigation via Multi-Task Reinforcement Learning and Probabilistic Perception#1201746
• Preference-Conditioned Multi-Objective Reinforcement Learning for Tactical Decision Making in Heavy-Duty Vehicles#1297025