Propose to Learn, Learn to Propose: Evaluability-Aware Assistance under Bounded Rationality

AI assistants often propose edits or plans that users must evaluate before adoption. While existing research focuses on proposal quality or goal inference, it often assumes users can reliably evaluate any proposal. This paper investigates how to plan proposals when users have bounded rationality, meaning they face cognitive costs when evaluating complex or distant changes. The authors ask: how can an assistant balance proposing high-value edits with selecting informative probes to learn about the user's evaluation constraints?

The authors formalize this as a Proposal-based Sequential assistancE (ProSE) problem, modeled as a Bayes-adaptive Markov decision process. They instantiate a binary response model where the probability of acceptance depends on the trade-off between the value gain of the proposal and a distance-dependent evaluability penalty. They analyze the structural consequences of this model, identifying an 'acceptance frontier' (where proposals are likely to be accepted) and an 'information frontier' (where proposals are most informative about the user's evaluability). They operationalize this with ProSE-Plan, a depth-2 Bayes-adaptive planner that scores proposals by considering both immediate responses and the resulting posterior belief updates.

The analysis reveals that likely-to-be-accepted proposals and informative probes do not necessarily coincide. Specifically, the most informative proposals about a user's evaluability often fall on the expected-rejection side of the acceptance frontier. In controlled graph simulations, ProSE-Plan outperforms evaluability-unaware and myopic baselines, particularly when evaluation cost is the bottleneck. Ablation studies confirm that the performance gain comes from response-dependent belief updates within the lookahead tree, rather than from lookahead alone.