PaperlayerView exact revision on arXiv

Source-linked AI summary

A Generalized Algorithm for Multi-Objective Reinforcement Learning and Policy Adaptation

Runzhe Yang, Xingyuan Sun, Karthik Narasimhan

arXiv:1908.08342v2cs.LGcs.AI

TL;DR

MORL must handle competing objectives whose relative preferences may vary, making a single fixed scalar-reward policy insufficient for new tasks. The paper introduces envelope Q-learning, which learns a preference-conditioned representation over the full preference space and adapts by conditioning on or inferring preferences. Across four domains, the approach is reported to outperform competitive baselines and to infer hidden preferences from very few trajectories.

  • Problem

    MORL must handle competing objectives whose relative importance varies across tasks, while prior scalarized or multi-policy approaches do not provide one policy optimized for each preference.

  • Method

    The method learns a single parametric representation over the preference space using a generalized Bellman optimality operator, convex-envelope updates, and deep neural networks.

  • Results

    Across four domains, the envelope algorithm achieves the best learning and adaptation performance among the evaluated MORL methods and can infer hidden preferences from few trajectories.

  • Takeaways & Limitations

    The learned model supports adaptation to specified preferences and preference elicitation on new tasks with scalar rewards and few sampled trajectories.

  • Takeaways & Limitations

    Direct optimization of the main loss is challenging because many discrete frontier solutions make the loss landscape considerably non-smooth.

Abstract

from arXiv · show

We introduce a new algorithm for multi-objective reinforcement learning (MORL) with linear preferences, with the goal of enabling few-shot adaptation to new tasks. In MORL, the aim is to learn policies over multiple competing objectives whose relative importance (preferences) is unknown to the agent. While this alleviates dependence on scalar reward design, the expected return of a policy can change significantly with varying preferences, making it challenging to learn a single model to produce optimal policies under different preference conditions. We propose a generalized version of the Bellman equation to learn a single parametric representation for optimal policies over the space of all possible preferences. After an initial learning phase, our agent can execute the optimal policy under any given preference, or automatically infer an underlying preference with very few samples. Experiments across four different domains demonstrate the effectiveness of our approach.

1 Introduction

MORL addresses competing objectives whose preferred trade-offs can vary by task, but existing approaches struggle to produce policies tailored to many preferences. The paper proposes one preference-conditioned model designed for optimal behavior across the preference space and few-shot adaptation.

  • Motivation: MORL optimizes several criteria simultaneously, so the optimal policy depends on the relative preferences among competing objectives.A virtual assistant may prioritize success rate or brevity depending on the user's task.
  • Motivation: Scalar reward design fixes objective trade-offs manually, limiting a learned policy's applicability when task preferences differ.MORL reduces dependence on scalar reward design and supports adaptation or transfer to related tasks with different preferences.
  • Challenge: Prior MORL strategies either scalarize objectives into an average policy or compute a set of optimal policies over the preference space.The introduction frames both strategies as the main existing approaches to learning across preferences.
  • Approach: The proposed algorithm learns a single policy network optimized over the entire preference space, using a generalized Bellman equation and convex-envelope alignment.The paper also targets convergence guarantees, deep-network scalability, and hidden-preference inference from scalar rewards.
  • Results: Across four domains, the methods significantly outperform competitive baselines and can infer hidden preferences from very few sampled trajectories.The reported domains include deep sea treasure, fruit tree navigation, task-oriented dialogue, and Super Mario Bros.

2 Background

The background formalizes linear-preference MORL around the convex coverage set, whose policies support optimal decisions for different preference vectors. The learning phase covers this set, while the adaptation phase selects or infers the policy needed for an unseen task.

  • MOMDP formulation: A MOMDP extends an MDP with vector rewards, a preference space, and preference functions that scalarize rewards; this paper considers linear scalarization.For linear preferences, utility is computed as ω⊺r(s, a).
  • CCS and preferences: The convex coverage set is the relevant subset of the Pareto frontier containing returns that maximize cumulative utility for some linear preference.For a given preference, the optimal CCS point has the largest projection along that preference's relative-importance direction.
  • Learning objective: The goal is to recover policies for the entire CCS and adapt to the optimal policy for any preference at test time, rather than solve for one unknown preference.The setup separates generalization across preferences from inference of a single hidden preference.
  • Two-phase setup: During learning, the agent obtains a set of optimal policies corresponding to the CCS, and ΠL(ω) determines the optimal policy for a given preference.The adaptation phase then handles either a human-specified preference or an unknown preference inferred for a new task.
  • Relation to prior work: Scalarized updates are described as sample-inefficient and sub-optimal because they cannot transfer value information across differently aligned preferences.Envelope Q-learning instead uses the convex envelope, and the paper adds convergence analysis, metrics, and broader benchmarks.

3 Multi-objective RL with Envelope Value Updates

Envelope Q-learning represents multi-objective values across preferences and updates them through an optimality operator over the convex solution envelope. The paper proves convergence, addresses nonsmooth optimization, and supports direct preference conditioning or hidden-preference adaptation.

  • Envelope Q-learning: Envelope Q-learning uses vectorized value functions and envelope updates to learn policies simultaneously across multiple preferences.Its updates use the convex envelope of the solution frontier rather than a single scalarized preference.
  • Optimality operator: The optimality filter selects the multi-objective Q-value maximizing scalar utility over both actions and candidate preferences, producing a preference-aligned envelope value.This permits more optimistic updates than a standard action-only Bellman filter.
  • Convergence theory: Theorem 1 establishes that the preferred optimal value function is a fixed point of the multi-objective optimality operator.The fixed-point result identifies Q* with T Q* under the paper's operator.
  • Convergence theory: Theorem 2 gives the contraction bound d(T Q, T Q′) ≤ γd(Q, Q′), and Theorem 3 guarantees convergence under repeated operator application.The resulting Q-functions are equivalent in utility for every preference, differing only at frontier recesses.
  • Learning algorithm: A single deep network takes state and preference as input and outputs action-by-objective Q-values, with sampled preferences and replay-based transitions used for training.The target uses the envelope maximization over candidate preferences and actions.
  • Optimization: Homotopy optimization shifts the loss from LA toward LB, while LA fits feasible rewards and LB pulls estimates toward directions with better utility.The auxiliary loss addresses the nonsmooth landscape created by many discrete frontier solutions.
  • Policy adaptation: At adaptation time, a supplied preference is fed into the learned model; with scalar rewards only, policy gradients and stochastic search infer hidden Gaussian preference parameters.The policy model remains fixed while preference parameters are optimized for expected return on the target task.

4 Experiments

The experiments evaluate MORL algorithms across four domains using coverage, adaptation, and utility measures. The envelope approach achieves the strongest overall learning and adaptation results, with advantages in scalability, sample efficiency, and preference adaptation.

  • Evaluation metrics: Coverage ratio measures recovery of optimal solutions in the convex coverage set, while adaptation error measures the gap from the optimal control frontier for specified preferences.Coverage ratio is based on precision and recall; adaptation error compares the agent’s control frontier with the optimal one.
  • Evaluation setup: Experiments cover deep sea treasure, fruit tree navigation, task-oriented dialog, and SuperMario using MORL baselines including MOFQI, CN+OLS, and Scalarized.DST and FTN use coverage ratio and adaptation error; Dialog and SuperMario use average utility over randomly sampled preferences.
  • Main results: The envelope algorithm achieves the best performance in both learning and adaptation among the evaluated MORL methods across all four domains.Table 1 reports means and standard deviations from five independent training and test runs, with statistical comparisons against the baselines.
  • Scalability: The envelope method remains more stable and outperforms Scalarized across FTN depths d = 5, 6, 7, although both methods worsen as the optimal policy set grows.The environments contain 32, 64, and 128 solutions at depths 5, 6, and 7, respectively.
  • Sample efficiency: The envelope algorithm consistently obtains better CR and AE with smaller variances and reaches the same AE using fewer sampled preferences than Scalarized.As the number of sampled preferences increases, CR improves and AE decreases for both algorithms.
  • Policy adaptation: In dialog, both MORL algorithms increase success rates as success preference weight rises, and envelope MORL outperforms other algorithms when that weight exceeds 0.5.Single-objective algorithms’ success rates do not change with the preference weight.
  • Preference inference: In SuperMario variant g4, the envelope agent identifies coin preference weight 0.6960 as best describing the task’s coin-collection goal.The learned preferences are concentrated on the diagonal, indicating alignment with the underlying preferences.

5 Conclusion

The paper introduces a linear-preference MORL algorithm that learns a single parametric representation of optimal policies across preferences. It provides convergence proofs and reports effective generalization, policy adaptation, and unknown-preference elicitation across four domains.

  • Conclusion: The method uses a multi-objective Bellman optimality operator to learn a single parametric representation for all optimal policies over the preference space.The paper targets few-shot adaptation of autonomous agents to new scenarios.
  • Conclusion: The paper provides convergence proofs for its multi-objective algorithm and demonstrates adaptation and preference elicitation on new tasks.The agent is evaluated across four domains for generalization and policy adaptation.

Supplementary Material for Generalized Algorithm for

The supplementary framework analyzes value-based reinforcement learning through value spaces, metrics, operators, and update schemes. It applies this framework to envelope MORL by representing preference-conditioned vector returns and using specialized replay and optimization updates.

  • General framework: Banach’s Fixed-Point Theorem provides the basis for iterative convergence when an operator is a contraction on a complete metric space.The theorem guarantees a unique fixed point and convergence from any initial point.
  • Convergence analysis: Minibatch updates with experience replay can converge under convergence and box conditions, even when restricted Q-value functions are updated asynchronously.The minibatch convergence theorem establishes pointwise convergence to Q∗ under its stated assumptions.
  • Convergence analysis: The convergence proof proceeds by showing that successive iterates eventually enter a nested sequence of shrinking sets.The induction uses state-action update times and the box condition to establish convergence to Q∗.
  • Approximate updates: If each n-round neural-network update remains within ϵ of the optimality operator, the final error is bounded by ϵ/(1 −γ).This bound follows from the contraction coefficient γ and the triangle inequality.
  • General framework: The framework comprises five elements: value space, value metric, evaluation operator, optimality operator, and updating scheme.The metric must support a complete metric space, while the operators define policy evaluation and optimality targets.
  • Envelope MORL: Envelope MORL changes the value space so Q-values map preferences to multi-objective vectors, preserving information needed for adaptation.The method combines this representation with a generalized optimality filter, hindsight experience replay, and homotopy optimization.

A.2.1 Multi-Objective Bellman Optimality Operator

The envelope Bellman optimality operator selects vector values associated with the best scalarized action-preference pair. It is a contraction whose iterations converge, under the generalized fixed-point result, to a value function equivalent to the preferred optimum.

  • Operators: The envelope evaluation operator applies the vector reward plus discounted expected future Q-values for a fixed policy and preference.Its form is analogous to single-objective Bellman evaluation and is a contraction.
  • Operators: The optimality filter H returns the multi-objective Q-value corresponding to the action-preference pair maximizing ωᵀQ.Because it uses the convex envelope of the current Pareto frontier, this filter motivates the name envelope version.
  • Operators: The envelope optimality operator combines immediate vector reward with the discounted expected filtered value: (T Q)(s, a, ω) := r(s, a) + γE[(H Q)(s′, ω)].The filter selects the vector value before the operator propagates it through the transition model.
  • Fixed-point result: The preferred optimal value function is a fixed point of the envelope optimality operator.The proof establishes equality of scalarized utilities for every state, action, and preference.
  • Contraction: The envelope operator satisfies d(T Q, T Q′) ≤γd(Q, Q′) for γ ∈[0, 1), establishing contraction in the envelope value space.The proof relies on the scalarization and argQ cancellation in the supremum expression.
  • Convergence: Despite the value distance being a pseudo-metric, repeated application of T converges to Q∗ under the generalized Banach fixed-point theorem.The limiting function may differ in values that produce identical utilities under the pseudo-metric.
  • Training updates: Hindsight replay associates each transition with multiple sampled preferences, expanding updates to minibatch_size × Nω.Because sampled preferences affect actions but not environment dynamics, trajectories can be replayed under arbitrary preferences.
  • Training updates: Homotopy optimization uses auxiliary losses to bring the vector Q-network toward the operator target and directly optimize the value metric.The target remains fixed during each loss optimization stage.

B.1 Domain Details

The paper evaluates envelope MORL across navigation, dialog, and game domains with competing objectives and preference-dependent policies. These environments test whether one learned model can maintain multiple optimal policies and adapt to specified or hidden preferences.

  • Deep Sea Treasure: The delayed-preference DST setting uses a convex Pareto frontier, so the frontier itself is the convex coverage set.This assumption makes all relevant frontier solutions available for preference-based evaluation.
  • Deep Sea Treasure: Deep Sea Treasure uses a 10 × 11 grid in which submarine navigation trades off a −1 time penalty against treasure value.The domain contains 10 treasures whose values increase with distance from the start.
  • Fruit Tree Navigation: Fruit Tree Navigation is a depth-d binary tree whose leaves carry six-dimensional nutrition rewards spanning Protein, Carbs, Fats, Vitamins, Minerals, and Water.Every leaf is optimal for some preference, so the agent must preserve paths to all leaves.
  • Fruit Tree Navigation: The FTN evaluation tests whether a preference-conditioned network finds all potential optimal paths and adapts when a preference is specified or hidden.The task is designed around unknown linear scalarization preferences.
  • Task-oriented dialog: The dialog domain optimizes task success and brevity, measured by success rate and number of turns, in a restaurant-reservation setting with simulated recognition errors.Learning covers unknown linear preferences, while adaptation must respond to a specified user preference under limited resources.
  • SuperMario: The SuperMario environment encodes five objectives, including horizontal progress, time, deaths, and coin collection.The adaptation evaluation uses 500 uniformly random preferences and up to 100 episodes for preference elicitation.

B.2 Implementation Details

Implementation combines preference-conditioned neural networks with off-policy reinforcement-learning techniques and parallel preference sampling. Training and evaluation budgets vary across the synthetic, dialog, and SuperMario domains.

  • Network architectures: Multi-objective Q-networks concatenate state representations with linear-preference parameters before producing action-related outputs.The networks use four fully connected hidden layers with widths scaled by dim(S) + m.
  • Network architectures: The SuperMario agent uses an envelope MoA3C variant with shared convolutional feature extraction followed by preference-conditioned actor and critic networks.Sixteen workers train in parallel with different sampled preferences.
  • Evaluation metrics: Coverage ratio measures discovery of potential optimal solutions, while adaptation quality measures policy adaptation to real-time specified preferences.These metrics correspond to the two central evaluation goals of MORL policy learning.
  • Optimization: DST and FTN training uses prioritized experience replay and double Q-learning to speed training and improve value estimates.The envelope target selects actions by maximizing ωᵀQ, with target-network copying every 100 steps.
  • Training schedules: Deep tree-navigation models use Adam with learning rate lr = 0.001 after replay-buffer warm-up and train for 5000 episodes.The replay memory size is 4000 and the batch size is 32.
  • Training schedules: Dialog policies train for 3,000 sessions and are evaluated on 5,000 sessions with randomly assigned user preferences.The preference distribution is nearly uniform, and single-objective baselines use several fixed preference groups.
  • Computing infrastructure: Experiments run on a workstation for synthetic and dialog tasks and on a 20-GPU cluster for SuperMario.The reported workstation includes one GeForce GTX TITAN X GPU, 12 CPUs, and 32G memory.

C.1 Evaluation Metrics

The evaluation uses Coverage Ratio (CR) to assess recovery of optimal solutions and Adaptation Quality (AQ) to assess preference-conditioned control performance. These metrics separately evaluate learning-phase coverage and adaptation-phase quality.

  • Coverage Ratio (CR): Coverage Ratio measures how many recovered solutions fall within a tolerance of the convex coverage set.CR uses precision, recall, and their harmonic mean, the F1 score, to characterize recovered optimal solutions.
  • Adaptation Quality (AQ): Adaptation Quality compares the retrieved control frontier with the optimal control frontier under a specified preference.AQ is based on the expected relative error between the optimal and agent control frontiers, scaled by α.
  • Adaptation Quality (AQ): Predictive AQ evaluates the accuracy of a multi-objective Q-network’s predicted control frontier.The predictive frontier is obtained from Q-network value predictions rather than executed trajectories.
  • Evaluation Settings: Experiments use positive, ℓ1-normalized Gaussian preference distributions, with α set to 0.01 for DST and 10.0 for FTN.The task-specific α values reflect the different penalty ranges in DST and value differences in FTN.

C.2 Deep Sea Treasure (DST)

On Deep Sea Treasure, the MORL algorithms recover the convex coverage set and closely reproduce the control frontier. The envelope algorithm achieves the best execution AQ, while the scalarized algorithm achieves the best predictive AQ.

  • Frontier Recovery: Both scalarized and envelope algorithms recover the entire convex coverage set in the Deep Sea Treasure task.The retrieved solutions include all potentially optimal solutions identified in the real CCS.
  • Frontier Recovery: The retrieved control frontier almost overlaps the real frontier, indicating strong alignment between preferences and optimal policies.The predicted control frontier is also shown during adaptation, alongside the real and retrieved frontiers.
  • Metric Comparison: The envelope algorithm achieves the best execution AQ, while the scalarized algorithm achieves the best predictive AQ.Table 4 distinguishes AQ measured on real adaptation trajectories from AQ measured on Q-function predictions.
  • Task Characteristics: The DST benchmark is relatively easy because its real CCS contains only 10 potentially optimal solutions.This small frontier allows the scalarized algorithm to solve the task efficiently.

C.3 Fruit Tree Navigation (FTN)

On Fruit Tree Navigation, envelope MORL improves coverage and sample efficiency across task depths and sampled-preference settings. It also provides multi-objective predictions and generally yields stronger or more stable adaptation behavior than scalarized MORL.

  • Sample Efficiency: As the number of sampled preferences increases, both algorithms’ CR and AQ increase, supporting better use of historical interactions.The sample-efficiency study trains for 5000 episodes and evaluates CR over 2000 episodes and AQ over 5000 episodes.
  • Coverage Ratio: The envelope algorithm has higher recall and lower variance than scalarized MORL across sampled-preference counts.Because every FTN solution is potentially optimal, precision is always 1, making recall and F1 the informative coverage measures.
  • Coverage Ratio: With more than one sampled preference per update, envelope MORL’s CR F1 score surpasses 0.98.Both algorithms improve as sampled preferences increase, while the envelope algorithm starts from stronger performance.
  • Frontier Size: At tree depth d = 5, both methods achieve CR F1 scores close to 1, but envelope MORL is more stable and can predict multi-objective solutions.Its prediction ability also improves as the number of sampled preferences increases.
  • Frontier Visualization: The envelope algorithm nearly covers the real CCS and has smaller control discrepancies than scalarized MORL.A small discrepancy remains at the frontier indentation, indicating an alignment issue between preferences and optimal policies.

C.4 Task-Oriented Dialog Policy Learning (Dialog)

In task-oriented dialog, envelope MORL performs strongly across preference-conditioned evaluation, especially for user utility and adaptation quality. Single-objective policies perform well mainly near the fixed preference used during training.

  • Overall Performance: Envelope MORL achieves the best average success rate, while equal-weight single-objective RL remains competitive.The comparison reports success rate, number of turns, user utility, and adaptation quality.
  • Adaptation Performance: Envelope MORL is significantly better than the other methods on average user utility and adaptation quality.The adaptation-quality comparison uses α = 0.1.
  • Preference Generalization: Envelope MORL is almost always better in utility under given preferences, whereas single-objective methods excel only near their fixed training preferences.The utility-weight curves average the closest 500 dialogues around each success-weight interval across three trained policies.

C.5 Multi-Objective SuperMario Game (SuperMario)

On SuperMario, the envelope MORL algorithm outperforms the scalarized baseline across three preference settings and supports few-shot preference adaptation. After 100 episodes, it infers preferences closer to the underlying objectives, though inferred preferences remain imperfect.

  • Performance comparison: The envelope algorithm outperforms the scalarized algorithm under fast-completion, coin-and-enemy, and uniform preferences.The uniform setting assigns weight 0.2 to each of five objectives: x-pos, time, death, coin, and enemy.
  • Training: EMoA3C converges within around 5k training episodes under a uniform probe preference.Figure 14 uses the probe preference [0.2 0.2 0.2 0.2 0.2] to sample evaluation trajectories.
  • Preference inference: After 100 adaptation episodes, EMoA3C infers preferences more concentrated on the diagonal and closer to the true underlying preferences than scalarized MoA3C.This comparison uses different SuperMario variants in which only corresponding scalar rewards are available.
  • Limitations: Inferred preferences are not exactly true because learned trade-off frontiers and policy-preference alignment can be imperfect, while close preferences may yield identical expected returns.The latter ambiguity persists even when the frontier and alignment are learned perfectly.
  • Preference inference: For achieving higher score in Mario, EMoA3C infers emphasis on x-pos (0.3725) and time (0.2307).This aligns with the strategy of moving Mario toward the flag within the time limit.
Loading 1908.08342v2…