Near-Minimax Multi-Objective RL under Predictable Adversarial Preferences and Preference-Free Exploration in Linear MDPs

Multi-objective reinforcement learning (MORL) must often support preferences that change online or are specified only after data collection. We study finite-horizon MORL with vector feedback in linear MDPs under two protocols: (i) predictable adversarial preferences revealed before each episode, and (ii) reward-free preference-free exploration (PFE), where exploration observes only transitions and must later answer arbitrary preference queries. Standard reductions are protocol-unsafe: re-scalarizing past stochastic rewards with future weights breaks the martingale structure needed for self-normalized confidence bounds, and hypervolume evaluation must account for episode-start randomization, which yields a deployable convex hull of return vectors. We propose a protocol-safe reward interface that estimates each reward coordinate via regression and performs scalarization only at query time, and we formalize deployable hypervolume semantics with a stability chain from support-function error to hypervolume error. Consequently, we obtain filtration-safe regret bounds for any predictable preference sequence without discretizing the simplex (only $\log m$ dependence) and matching near-minimax rates in linear MDPs, as well as sharp reward-free PFE guarantees: a (near-)minimax decision-optimal query answering rate $\tilde{O}(d^2 U_{\mathrm{ret}}^2/\varepsilon^2)$ and a tight separation from explicit transition-model recovery $\Theta(d(|\mathcal{S}|-1)/\varepsilon_P^2)$. These results connect online learning, preference-free deployment, and hypervolume-aware evaluation through a single protocol-aligned theory.

Many AI systems need to balance several goals at once. For example, a robot may need to be fast, safe, and energy-efficient, while different users may care about these goals in different ways. A common shortcut is to combine past outcomes using whatever preference is chosen later, but this can make the learning process statistically unreliable. This paper studies how to learn when preferences can change from one trial to the next, or when preferences are only specified after data has already been collected. Our method keeps separate estimates for each goal and combines them only when a particular preference is requested. We also explain how to evaluate the set of trade-offs that can actually be deployed when randomized choices between decision rules are allowed. The results show that this protocol-aware approach can achieve strong learning guarantees while avoiding an expensive search over all possible preferences.