Preference-Uncertainty Aware Planning With Coverage Guarantees

AI-assisted planning agents, increasingly enabled by generative-AI, require recommendations that are certifiably aligned with the user; yet users can rarely articulate their preferences upfront and can only provide noisy comparative feedback. We formalize this as preference elicitation over an unknown linear utility on a multidimensional KPI space where the goal is to recommend a near-optimal action in few queries, with a high-probability guarantee. We introduce a two-phase algorithm with end-to-end coverage. Phase one propagates an upstream conformal prediction set on the preference vector through the utility-maximization problem, yielding the set of plausibly optimal actions. Phase two queries the user with menus of these actions and uses e-processes to eliminate actions inconsistent with the responses, stopping when minimax regret falls below a tolerance $\varepsilon$. The returned action is $\varepsilon$-optimal for the true preference with probability at least $1-\alpha-\delta$ for $\alpha>0$ from the conformal guarantee and $\delta>0$ from the e-process.