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