PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Multi-Objective Sequential Decision-Making

Diederik Marijn Roijers, Peter Vamplew, Shimon Whiteson, Richard Dazeley

arXiv:1402.0590v1cs.AI

TL;DR

Multi-objective sequential decision-making lacks clear guidance on when specialized methods are needed instead of single-objective reductions. The paper surveys existing planning and learning algorithms, identifies three motivating scenarios, and proposes a taxonomy linking assumptions, scalarization, and policy types to solution forms. It concludes that optimal solutions may be single policies, coverage sets, convex coverage sets, or Pareto fronts, depending on these factors.

  • Problem

    Existing multi-objective sequential decision-making literature is growing but fragmented and often leaves unclear when single-objective reduction is impossible, infeasible, or undesirable.

  • Method

    The paper surveys planning and learning methods using a taxonomy based on motivating scenario, scalarization function, and whether deterministic or stochastic policies are considered.

  • Results

    The taxonomy shows that these factors determine whether the optimal solution is a single policy, a coverage set, a convex coverage set, or a Pareto front.

  • Takeaways & Limitations

    The three scenarios clarify when multi-objective methods are needed and represent the main ways such methods are applied in practice.

  • Takeaways & Limitations

    Bellman-based planning and learning methods rely on additive returns, which some multi-objective settings disrupt and thereby make inapplicable.

Abstract

from arXiv · show

Sequential decision-making problems with multiple objectives arise naturally in practice and pose unique challenges for research in decision-theoretic planning and learning, which has largely focused on single-objective settings. This article surveys algorithms designed for sequential decision-making problems with multiple objectives. Though there is a growing body of literature on this subject, little of it makes explicit under what circumstances special methods are needed to solve multi-objective problems. Therefore, we identify three distinct scenarios in which converting such a problem to a single-objective one is impossible, infeasible, or undesirable. Furthermore, we propose a taxonomy that classifies multi-objective methods according to the applicable scenario, the nature of the scalarization function (which projects multi-objective values to scalar ones), and the type of policies considered. We show how these factors determine the nature of an optimal solution, which can be a single policy, a convex hull, or a Pareto front. Using this taxonomy, we survey the literature on multi-objective methods for planning and learning. Finally, we discuss key applications of such methods and outline opportunities for future work.

1. Introduction

Sequential decision-making is widely modeled with scalar rewards, but many practical tasks involve conflicting objectives. The article surveys multi-objective algorithms and introduces a taxonomy to clarify when and how specialized methods apply.

  • Sequential decision-making supports applications including robotics, games, clinical management, military planning, and infrastructure control.
  • Many tasks are more naturally represented by multiple conflicting objectives, such as minimizing traffic latency while maximizing throughput.
  • The article surveys algorithms for multi-objective sequential decision-making and formalizes the setting as a multi-objective MDP.
  • The paper identifies three scenarios where multi-objective problems cannot be trivially reduced to single-objective problems.
  • Its taxonomy organizes methods by assumptions and the nature of their resulting solutions, while the survey covers planning, learning, applications, and future directions.

2. Background

The paper defines MDPs through states, actions, transitions, rewards, initial-state distributions, and discounting, then contrasts scalar values with vector-valued MOMDP returns. Multiple objectives create only partial policy orderings, requiring scalarization or other preference information.

  • A finite discounted MDP comprises states, actions, transitions, rewards, an initial-state distribution, and a discount factor.
  • MDP returns are typically additive discounted sums, and the Bellman equation recursively expresses values for stationary policies.
  • An agent’s policy determines action selection, while stationary policies condition only on the current state and may be deterministic or stochastic.
  • Methods relying on Bellman recursion may become inapplicable when multi-objective scalarization disrupts additive returns.
  • Standard additive infinite-horizon single-objective MDPs have at least one deterministic stationary optimal policy.
  • A MOMDP replaces scalar rewards and values with vectors of rewards and expected cumulative discounted returns across objectives.
  • Because vector values impose only partial orderings, identifying optimal policies requires additional information about objective priorities, such as a scalarization function.

3. Motivating Scenarios

The paper motivates multi-objective methods through three scenarios: weights may be unknown, scalarization may be infeasible to specify, or scalarization may be undesirable despite known weights. These scenarios determine whether methods produce multiple policies or one executable policy.

  • The reward hypothesis suggests converting multi-objective problems into single-objective MDPs with additive returns through scalarization and reward redesign.
  • A scalarization function projects a multi-objective value to a scalar, with a weight vector parameterizing the function.
  • Unknown weights scenario: In the unknown weights scenario, scalarization is impossible before planning or learning but becomes trivial when the policy is executed because the weights are then known.
  • Decision support scenario: In the decision support scenario, preferences or scalarization may be too difficult to quantify, so methods compute an optimal solution set under known constraints.
  • Known weights scenario: In the known weights scenario, scalarization is feasible but may be undesirable because nonlinear returns can lose additivity or cause state-space blowup.
  • The three scenarios can also apply online, where planning or learning is interleaved with execution and previously unknown weights may become dynamic.

4. Problem Taxonomy

The taxonomy derives the appropriate solution concept from assumptions about scalarization, policy multiplicity, and policy stochasticity. It uses a utility-based approach to justify the Pareto front when appropriate while allowing other solution concepts when it is not.

  • The utility-based approach selects a policy by collapsing its value vector to a scalar utility through a scalarization function.Scalarization may be implicit in the user's thought process but remains part of what the agent should maximize.
  • The utility-based approach derives the solution concept from the problem rather than assuming that the optimal solution set is always the Pareto front.When the Pareto front is appropriate, this approach provides a justification; otherwise, it permits another solution concept.
  • The taxonomy classifies MOMDPs by scalarization assumptions, whether one or multiple policies are sought, and whether policies may be stochastic.These factors determine the nature of the optimal solution.
  • The taxonomy contrasts linear scalarization with merely monotonically increasing scalarization functions.It also distinguishes single-policy from multiple-policy settings and deterministic from stochastic policies.
  • The taxonomy aims to cover most MOMDP research while remaining simple and intuitive, although some research does not fit neatly within it.The survey notes such discrepancies when discussing planning and learning methods.

4.1 Single versus Multiple Policies

Whether an MOMDP requires one or multiple policies depends on the motivating scenario and when user preferences become available. Multiple-policy settings return a set of undominated policies sufficient to cover possible scalarizations, followed by policy selection for execution.

  • Single versus Multiple Policies: The unknown weights and decision support scenarios require multiple policies because planning or learning occurs before the relevant preference information is available or applied.Both scenarios separate planning or learning from execution.
  • Single versus Multiple Policies: An undominated policy is optimal for at least one weight, whereas a coverage set contains enough policies to include an optimal policy for every possible weight.The undominated set may contain redundant policies, while a coverage set need not.
  • Single versus Multiple Policies: Coverage sets need not be unique because multiple policies can share scalarized values, allowing redundant alternatives to be omitted.The undominated set is unique, but a coverage set may choose only one policy among equally valued alternatives.
  • Single versus Multiple Policies: Ideally, an algorithm finds the smallest coverage set, although finding a smaller set than the full undominated set may be easier.
  • Single versus Multiple Policies: In the execution phase, one policy is selected from the returned set; when weights are revealed beforehand, selection maximizes scalarized value among those policies.In decision support, users manually inspect the set and make an implicit trade-off between objectives.
  • Single versus Multiple Policies: The known weights scenario seeks one policy because weights are known before planning or learning begins.Scalarization may nevertheless produce a difficult single-objective MDP.

4.2 Linear versus Monotonically Increasing Scalarization Functions

The scalarization function determines which policies can be retained and what constitutes an optimal solution. Linear scalarization yields convex-hull-based solutions, whereas broader monotonically increasing functions require Pareto-based coverage.

  • Linear Scalarization Functions: Linear scalarization computes the inner product of objective weights and a policy’s multi-objective value vector.Weights are positive real numbers constrained to sum to 1.
  • Linear Scalarization Functions: When weights are known, linear scalarization distributes over addition, producing an additive single-objective MDP solvable by standard methods.The resulting solution is a single deterministic stationary policy.
  • Linear Scalarization Functions: When weights are unknown during planning or learning, linear scalarization uses a convex hull containing policies optimal for some weight vector.A convex coverage set retains a policy with maximal linearly scalarized value for every weight vector and can remove superfluous convex-hull policies.
  • Linear Scalarization Functions: For non-stationary or stochastic policies, the convex hull may contain infinitely many policies even when a finite convex coverage set exists.For deterministic stationary policies, the difference between these sets may be small.
  • Monotonically Increasing Scalarization Functions: Nonlinear scalarization can destroy additivity of scalarized returns, making linear-scalarization optimality notions inappropriate and affecting which planning or learning methods apply.For strictly monotonically increasing functions, Pareto coverage is the general solution concept; for merely monotonically increasing functions, a Pareto coverage set can be used.
  • Monotonically Increasing Scalarization Functions: Strictly monotonically increasing scalarization permits retaining the Pareto front, because every policy outside it is dominated and cannot be optimal.Unlike linear scalarization, the exact shape of the function may be unknown; the Pareto front can therefore be the relevant coverage set.

4.3 Deterministic versus Stochastic Policies

The policy class allowed—deterministic or stochastic, stationary or non-stationary—changes which solutions are attainable and required in multi-objective MDPs. Unlike single-objective additive MDPs, nonlinear scalarization can require non-stationary, stochastic, or history-dependent policies.

  • Policy restrictions are consequential in MOMDPs, whereas single-objective additive MDPs always have a deterministic stationary optimal policy.The taxonomy therefore distinguishes deterministic from stochastic and stationary from non-stationary policies.
  • 4.3.1 Deterministic and Stochastic Policies with Linear Scalarization Functions: With linear scalarization, a deterministic stationary policy optimal for each weight vector suffices, even when stochastic and non-stationary policies are allowed.The vector reward is scalarized by an inner product, preserving additive returns and enabling translation to a single-objective MDP.
  • 4.3.3 Multiple Stochastic Policies with Monotonically Increasing Scalarization Functions: For nonlinear scalarization with stochastic policies allowed, mixture policies over deterministic stationary policies can generate a convex coverage set.An infinite set of mixture policies constructed from a convex coverage set is itself a Pareto coverage set.
  • Pareto coverage sets are necessary only with monotonically increasing scalarization and deterministic policies; linear scalarization or stochastic policies instead requires a convex coverage set.This observation identifies the specific setting in which Pareto optimality is the relevant solution concept.
  • For nonlinear scalarization, optimal policies can depend on reward history because scalarized returns are no longer additive.In the example, the preferred action changes according to the accumulated reward history, even at the same state.

5. Planning in MOMDPs

Planning methods for MOMDPs are organized by scalarization and policy setting, with specialized approaches needed when nonlinear scalarization breaks additive-return assumptions. The survey covers direct methods and transformations to POMDPs, while noting efficiency and scope limitations.

  • MOMDP planning computes an optimal policy or a coverage set of undominated policies from a complete transition and reward model.The survey first separates single-policy planning from multiple-policy planning, then organizes methods by scalarization function.
  • 5.1 Single-Policy Planning: For known weights and linear scalarization, an MOMDP can be transformed into a single-objective MDP; nonlinear scalarization requires specialized planning because returns may be non-additive.Non-additivity makes standard dynamic programming and linear programming methods based on the Bellman equation inapplicable.
  • 5.2 Multiple-Policy Planning with Linear Scalarization Functions: For multiple policies with linear scalarization, planners seek a convex coverage set, including through MOMDP-to-POMDP translation and specialized convex-hull methods.The POMDP translation represents the unknown true objective as a hidden state component while the MOMDP state remains known.
  • 5.2 Multiple-Policy Planning with Linear Scalarization Functions: The POMDP transformation is inefficient because it ignores MOMDP structure, and general infinite-horizon POMDPs are undecidable although MOMDP convex coverage sets can be computed exactly.The translated problem has a known state component and observations that reveal nothing about the hidden objective component.
  • 5.2 Multiple-Policy Planning with Linear Scalarization Functions: Convex hull value iteration stores sets of value vectors for state-action pairs and propagates their convex hulls during backups.The vectors represent optimal Q-values for all possible weight vectors.
  • 5.2 Multiple-Policy Planning with Linear Scalarization Functions: Finite-horizon spline-based value iteration improves asymptotic time and space complexity over CHVI and extends to continuous states, but the original algorithm supports only two objectives.Subsequent work extends the approach to an arbitrary number of objectives and provides a three-objective implementation.
  • 5.3 Multiple-Policy Planning with Monotonically Increasing Scalarization Functions: For nonlinear scalarization, finding a Pareto coverage set is problematic because infinitely many weights remain and scalarized returns may be non-additive.These issues can make repeated single-objective methods inapplicable and prevent straightforward Bellman-based extensions.

6. Learning in MOMDPs

Multi-objective reinforcement learning adapts planning ideas to unknown environments, with standard methods sufficient for linear scalarization but substantial challenges under nonlinear scalarization. The survey groups nonlinear methods by how they address non-additive returns.

  • MORL is used when the MOMDP transition and reward model is unavailable, either by learning a model for later planning or directly learning policies.Only a few surveyed papers use model-based MORL, while most work is model-free.
  • Multiple-policy MORL can remain practical through model-based learning or off-policy methods that reuse data across weight settings.Off-policy learning allows policies for multiple weights to be optimized using the same data.
  • 6.1 Single-Policy Learning: Under known weights and linear scalarization, MORL reduces to single-objective MDP learning, so standard temporal-difference methods such as Q-learning apply directly.Some methods instead learn vector-valued value functions and scalarize only during action selection.
  • 6.1 Single-Policy Learning: Nonlinear scalarization is challenging because it can produce non-additive returns, undermining temporal-difference methods based on the Bellman equation.The survey reports four main classes: unmodified TD heuristics or restricted methods, modified TD or state representations, meta-policies over linear-scalarization policies, and policy search.
  • 6.1 Single-Policy Learning: The four nonlinear-scalarization classes include multi-agent approaches, modified TD or state representations, meta-policies built from linear policies, and policy-search methods.Policy search avoids the Bellman equation and can therefore be applied directly with nonlinear scalarizations.
  • 6.1 Single-Policy Learning: TD methods combined with nonlinear scalarization may converge only under certain conditions and can otherwise converge to suboptimal policies or fail to converge.One reported example is TLO failing to converge suitably in episodic tasks when a constrained objective receives non-terminal non-zero rewards.
  • 6.2 Multiple-Policy Learning with Linear Scalarization Functions: For multiple-policy linear scalarization, methods learn or approximate a convex coverage set, but many samples may still be needed before obtaining a good approximation.MOFQI generalizes across both state-action space and weight space by including weights in the function approximator input.

7. MOMDP Applications

MOMDP methods have been applied across diverse domains, including environmental management, finance, communications, industrial control, robotics, and traffic infrastructure. Researchers also connect multi-objective sequential decision-making to broader classes such as probabilistic planning, risk-aware reinforcement learning, and model checking.

  • Specific applications: Applications span environmental management, financial markets, information and communications technology, industrial control, robotics, and traffic infrastructure.The survey covers both specific applications and broader classes of problems.
  • Environmental management: Reservoir control balances hydroelectric production with flood mitigation and other uses of stored water.This is described as one of the most extensively researched applications.
  • Environmental management: SAVES targets a trade-off between commercial-building energy consumption and occupant comfort.Simulation results indicate approximately 30% lower energy consumption than manual control.
  • Finance and communications: MORL applications balance objectives such as financial profit and spread, cloud responsiveness, resource utilization and fairness, or communication throughput and equity.Constrained MORL also minimizes transmission delay while maintaining an acceptably low packet-loss rate.
  • Robotics and control: Robotic applications commonly balance progress toward a target with collision avoidance, while some work remains primarily simulation-based.Collision reduction may be more reasonable than requiring a collision-free policy when obstacles are fast and difficult to predict.
  • Broader problem classes: Multi-objective decision-making is linked to uncertainty-aware planning because expected return may be insufficient without considering return variance or transitions into error states.Related work also connects these methods with risk-aware reinforcement learning and probabilistic model checking.

8. Future Work

Future work targets understudied model-based and many-objective settings, preference-guided search, and objective formulations suited to one-shot policy execution. The survey also highlights unresolved challenges involving deterministic policies and the distinction between scalarizing expected returns versus individual returns.

  • Model-based methods: Model-based MORL remains understudied despite the breadth of MOMDP planning methods available as potential subroutines.The survey identifies spline-based multi-objective value iteration from historical transition and reward data as a rare example.
  • Policy classes: When only deterministic policies are permitted, learning the required coverage set is more difficult than when stochastic policies allow mixtures or stationary randomizations.Finite-horizon approximations are suggested as one possible approach to infinite-horizon problems.
  • Many-objective decision-making: Many-objective sequential decision-making is challenging because undominated solutions typically grow exponentially with the number of objectives.Interactive preference articulation is recommended to restrict search to a smaller region of interest.
  • Many-objective decision-making: The survey highlights an eight-objective jet-engine control system as an example of a naturally many-objective engineering problem.Such problems have received comparatively little consideration in MOMDP research.
  • Return formulations: Expectation of Scalarized Return is particularly relevant when a policy is executed only once, whereas Scalarization of Expected Return suits returns accumulated across repeated episodes.The two formulations can prefer different policies in the same MOMDP.

9. Conclusions

The survey identifies when multi-objective methods are needed, organizes them through a taxonomy, reviews planning and learning research, and surveys applications. It concludes with understudied directions including model-based learning, monotonically increasing scalarizations, many-objective problems, and one-shot return optimization.

  • Contributions: The survey identifies three scenarios in which conversion to a single-objective problem is impossible, infeasible, or undesirable.These scenarios also represent the main ways multi-objective methods are applied in practice.
  • Taxonomy: Its taxonomy classifies methods by scenario, scalarization function, and policy type, determining whether an optimal solution is a single policy or a coverage set.Coverage sets may be convex or Pareto, and a convex coverage set of deterministic stationary policies is often sufficient.
  • Literature survey: The survey finds that most learning methods are model-free rather than model-based, leaving model-based approaches understudied.Learning with monotonically increasing scalarization functions is another sparsely studied area.
  • Applications: Applications cover environmental management, financial markets, information and communications technology, industrial processes, robotics, and traffic infrastructure.The survey also connects MOMDP research with probabilistic planning, model checking, multi-agent systems, and multi-objective optimization.
  • Future work: Future directions include model-based methods, monotonically increasing scalarization settings, many-objective sequential decision-making, and Expectation of Scalarized Return.Expectation of Scalarized Return is especially important when a policy can be executed only once.
Loading 1402.0590v1…