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

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

Research Team and Affiliations

Abstract

Personalizing multi-objective decisions—such as selecting a route based on a trade-off between speed, fuel efficiency, and scenery—is challenging because users often cannot articulate their exact numerical preferences. This paper introduces a framework to identify a near-optimal personalized policy using only simple "A vs. B" comparisons. The proposed approach requires a number of queries that scales quasilinearly with the number of objectives, offering a scalable solution for complex decision-making tasks.

Introduction

In standard Reinforcement Learning (RL), agents typically optimize for a single scalar reward. However, real-world decisions are rarely so simple. A navigation application, for instance, must consider travel time, fuel consumption, road quality, and safety. The primary difficulty in these multi-objective settings is that every user balances these objectives differently. While one might prioritize the fastest route, another might prefer a more fuel-efficient path even if it takes longer.

Directly eliciting these preferences is difficult; most humans cannot accurately provide the exact numerical weights they assign to different objectives. However, humans are adept at making comparative judgments—stating a preference for one option over another. This paper addresses the challenge of efficiently finding the single best policy for a specific user using only a limited number of comparative "A vs. B" questions.

Methodology

The authors model the problem as a Markov Decision Process (MDP) with a vector-valued reward function, where each dimension represents a different objective. They assume the user has a hidden "preference vector" that linearly combines these objectives into a single utility.

The paper introduces two primary algorithmic contributions:

1. Preference Estimation via Policy Mixing

To estimate the hidden preference vector, the algorithm identifies a "basis" of policies that span the reward space. It then utilizes a binary search technique combined with a "do nothing" anchor—a baseline policy that yields zero reward. By mixing a candidate policy with this "do nothing" baseline, the agent can create a spectrum of options. By observing where a user becomes indifferent between two choices, the algorithm can mathematically pinpoint the relative weights of the objectives.

2. Interpretable Policy Representation

Comparing abstract, stochastic policies is cognitively demanding for human users. To facilitate intuitive comparisons, the authors provide an algorithm to compress any complex policy into a weighted trajectory set. Leveraging Carathéodory’s theorem, they demonstrate that any policy can be perfectly represented by just $k+1$ example paths (where $k$ is the number of objectives). This allows users to compare concrete examples rather than probability distributions, making the feedback process significantly more accessible.

Key Insights and Theoretical Results

The framework's efficiency is a major highlight. The authors prove that the number of queries required scales as $O(k \log(k/\epsilon))$, meaning that doubling the number of objectives only roughly doubles the number of questions required, avoiding the exponential explosion common in high-dimensional preference elicitation.

Furthermore, the algorithms run in polynomial time relative to the size of the MDP (states and actions), ensuring practical applicability. The authors also provide rigorous theoretical bounds on the sub-optimality of the final policy, demonstrating that the algorithm converges to a high-quality solution even when users cannot distinguish between very similar options.

Discussion and Future Work

While the current framework provides a robust solution for known environments with linear preferences, several areas for future exploration remain. Currently, the model assumes the environment's dynamics are known; integrating environment learning with preference elicitation is a natural next step. Additionally, human preferences can be non-linear or involve specific thresholds (e.g., "safety must be above a certain level regardless of speed"). Extending the framework to handle non-linear preferences and noisier user feedback will be crucial for broader real-world deployment.

Conclusion

By combining geometric principles with efficient search strategies, this work provides a scalable and interpretable approach to personalizing multi-objective decisions. The ability to derive optimal policies from simple comparative feedback, while maintaining theoretical guarantees on query complexity, represents a significant advancement in user-centric reinforcement learning.

Summary updated

Abstract

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 known 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 number of comparison queries that scales quasilinearly in the number of objectives.
BibTeX
@inproceedings{shao2023eliciting,
  author = {Han Shao and Lee Cohen and Avrim Blum and Yishay Mansour and Aadirupa Saha and Matthew 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