Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback

Han Shao, Lee Cohen, Avrim Blum, Yishay Mansour, Aadirupa Saha, Matthew R. Walter

TL;DR

This paper introduces a novel framework for personalized multi-objective decision-making by learning user preferences through comparative feedback. It proposes efficient algorithms to find near-optimal policies for individual users by asking them to compare different policy options, rather than requiring explicit preference declarations.

What Problem Does This Paper Address?

Many real-world decision-making problems, from designing investment portfolios to navigating with GPS, involve balancing multiple objectives. The "best" way to balance these objectives is highly subjective and varies from person to person. Traditional approaches often optimize for a single scalar reward or a Pareto-optimal set, which doesn't account for individual user preferences. This paper tackles the challenge of efficiently learning these personalized preferences and finding a policy that's optimal for a specific user, using a more intuitive feedback mechanism: comparing two options.

Methods

The authors propose a framework based on Markov Decision Processes (MDPs) with vector-valued rewards. User preferences are modeled as an unknown, hidden vector representing the relative importance of each objective. The core of their approach lies in eliciting these preferences through comparative feedback. They explore two feedback models:

  1. Policy Comparison: Users are shown two policies and asked to choose their preferred one.
  2. Weighted Trajectory Set Comparison: Users compare two small sets of representative trajectories, each with associated weights, and choose the preferred set.

For both models, they develop algorithms that efficiently learn the user's preference vector and then derive a near-optimal policy. A key technique involves finding a set of "basis policies" whose value vectors are linearly independent, which helps in estimating the preference vector. They also introduce a method to represent policies as weighted trajectory sets, making the feedback more interpretable for users.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Comparative Feedback is Powerful and Intuitive: Users find it easier to compare options than to explicitly state their preferences. This makes the proposed feedback mechanism more practical for real-world applications.
  • Personalization is Key for Multi-Objective Problems: A single "optimal" policy for multiple objectives is often insufficient. Tailoring policies to individual user preferences is crucial for effective decision-making.
  • Weighted Trajectory Sets as Interpretable Policy Representations: Representing policies as a small set of representative trajectories with weights offers a more understandable way for users to provide feedback compared to raw state-action mappings.
  • Efficient Learning via Basis Policies: By identifying a set of linearly independent policy values, the authors can efficiently estimate the user's preference vector, even with limited queries.

Key Results

The paper presents algorithms that can find a nearly optimal personalized policy for a user using a number of comparison queries that scales quasilinearly with the number of objectives. Specifically, they achieve theoretical guarantees for the number of queries required, which is polynomial in the number of objectives and logarithmic in the desired precision. The algorithms are designed to be efficient, with computational complexity that is polynomial in the MDP's horizon, state space, and action space.

Limitations and Future Work

  • Unknown MDP: The current work assumes the MDP is known. An interesting future direction is to relax this assumption and learn the model first, then apply the preference elicitation algorithms. The sub-optimality would then depend on both model estimation error and preference learning error.
  • Dependency on Epsilon: The authors note that the dependency on epsilon (a measure of feedback precision) in their theorems might not be optimal and leaves it as an open problem. They suggest exploring ways to improve this bound.
  • Hyperparameter Tuning: One of the proposed algorithms requires setting a hyperparameter related to the feedback precision, which can be challenging. They suggest a method to estimate this parameter but acknowledge that an improper value could degrade performance.

Summary updated

Abstract

In classic reinforcement learning (RL) and decision making problems, policies are evaluated with respect to a scalar reward function, and all optimal policies are the same with regards to their expected return. However, many real-world problems involve balancing multiple, sometimes conflicting, objectives whose relative priority will vary according to the preferences of each user. Consequently, a policy that is optimal for one user might be sub-optimal for another. In this work, we propose a multi-objective decision making framework that accommodates different user preferences over objectives, where preferences are learned via policy comparisons. Our model consists of a Markov decision process with a vector-valued reward function, with each user having an unknown preference vector that expresses the relative importance of each objective. The goal is to efficiently compute a near-optimal policy for a given user. We consider two user feedback models. We first address the case where a user is provided with two policies and returns their preferred policy as feedback. We then move to a different user feedback model, where a user is instead provided with two small weighted sets of representative trajectories and selects the preferred one. In both cases, we suggest an algorithm that finds a nearly optimal policy for the user using a small number of comparison queries.
BibTeX
@inproceedings{shao2023eliciting,
  author = {Han Shao and Lee Cohen and Avrim Blum and Yishay Mansour and Aadirupa Saha and Matthew R. Walter},
  title = {{Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=PYASzxr2OP},
}
Figure