Multi-Objective Decision Making

✍ Scribed by Diederik M. Roijers, Shimon Whiteson

• Publisher: Springer
• Year: 2017
• Tongue: English
• Leaves: 122
• Series: Synthesis Lectures on Artificial Intelligence and Machine Learning
• Edition: 1
• Category: Library

✦ Synopsis

Many real-world decision problems have multiple objectives. For example, when choosing a medical treatment plan, we want to maximize the efficacy of the treatment, but also minimize the side effects. These objectives typically conflict, e.g., we can often increase the efficacy of the treatment, but at the cost of more severe side effects. In this book, we outline how to deal with multiple objectives in decision-theoretic planning and reinforcement learning algorithms. To illustrate this, we employ the popular problem classes of multi-objective Markov decision processes (MOMDPs) and multi-objective coordination graphs (MO-CoGs).

First, we discuss different use cases for multi-objective decision making, and why they often necessitate explicitly multi-objective algorithms. We advocate a utility-based approach to multi-objective decision making, i.e., that what constitutes an optimal solution to a multi-objective decision problem should be derived from the available information about user utility. We show how different assumptions about user utility and what types of policies are allowed lead to different solution concepts, which we outline in a taxonomy of multi-objective decision problems.

Second, we show how to create new methods for multi-objective decision making using existing single-objective methods as a basis. Focusing on planning, we describe two ways to creating multi-objective algorithms: in the inner loop approach, the inner workings of a single-objective method are adapted to work with multi-objective solution concepts; in the outer loop approach, a wrapper is created around a single-objective method that solves the multi-objective problem as a series of single-objective problems. After discussing the creation of such methods for the planning setting, we discuss how these approaches apply to the learning setting.

Next, we discuss three promising application domains for multi-objective decision making algorithms: energy, health, and infrastructure and transportation. Finally, we conclude by outlining important open problems and promising future directions.

✦ Table of Contents

Cover
Copyright Page
Title Page
Contents
Preface
Acknowledgments
Table of abbreviations
Introduction
Motivation
Utility-based Approach
Multi-Objective Decision Problems
Multiple Objectives
Multi-Objective Coordination
Single-Objective Coordination Graphs
Multi-Objective Coordination Graphs
Multi-Objective Markov Decision Processes
Single-Objective Markov Decision Processes
Multi-Objective Markov Decision Processes
Taxonomy
Critical Factors
Single vs. Multiple Policies
Linear vs. Monotonically Increasing Scalarization Functions
Deterministic vs. Stochastic Policies
Solution Concepts
Case #1: Linear Scalarization and a Single Policy
Case #2: Linear Scalarization and Multiple Policies
Case #3: Monotonically Increasing Scalarization and a Single Deterministic Policy
Case #4: Monotonically Increasing Scalarization and a Single Stochastic Policy
Case #5: Monotonically Increasing Scalarization and Multiple Deterministic Policies
Case #6: Monotonically Increasing Scalarization and Multiple Stochastic Policies
Implications for MO-CoGs
Approximate Solution Concepts
Beyond the Taxonomy
Inner Loop Planning
Inner Loop Approach
A Simple MO-CoG
Finding a PCS
Finding a CCS
Design Considerations
Inner Loop Planning for MO-CoGs
Variable Elimination
Transforming the MO-CoG
Multi-Objective Variable Elimination
Comparing PMOVE and CMOVE
Inner Loop Planning for MOMDPs
Value Iteration
Multi-Objective Value Iteration
Pareto vs. Convex Value Iteration
Outer Loop Planning
Outer Loop Approach
Scalarized Value Functions
The Relationship with POMDPs
Optimistic Linear Support
Analysis
Approximate Single-Objective Solvers
Value Reuse
Comparing an Inner and Outer Loop Method
Theoretical Comparison
Empirical Comparison
Outer Loop Methods for PCS Planning
Learning
Offline MORL
Online MORL
Applications
Energy
Health
Infrastructure and Transportation
Conclusions and Future Work
Conclusions
Future Work
Scalarization of Expectation vs. Expectation of Scalarization
Other Decision Problems
Users in the Loop
Bibliography
Authors' Biographies