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

Yifan Zhu; Sammie Katt; Samuel Kaski

Source-linked AI summary

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

Yifan Zhu, Sammie Katt, Samuel Kaski

arXiv:2609.02242v1Sep 2, 2026cs.AIcs.HCcs.MA

TL;DR

AI assistance that relies on user evaluation must account for bounded evaluability, not only proposal quality or inferred preferences. The paper formalises proposals as both interventions and probes, develops a bounded-rational binary response model, and uses a depth-2 Bayes-adaptive planner. The planner improves in controlled settings where evaluation cost is the bottleneck, while analysis shows that informative proposals can be likely to receive rejection.

Problem
Existing proposal-based assistance often models user goals without accounting for whether users can evaluate particular proposals under cognitive and computational constraints.
Method
ProSE models proposals as task interventions and information probes, using a KL-regularised binary response likelihood with a distance-dependent evaluability penalty and a depth-2 Bayes-adaptive planner.
Results
0.815 success for PROSE-PLAN versus 0.550 for PERSONALISED-MYOPIC and 0.555 for BELIEF-FROZEN DEPTH-2 in the branching-corridor task.
Takeaways & Limitations
Likely accepted proposals and informative probes need not coincide, making user evaluability a planning-relevant dimension complementary to generation quality and preference inference.
Takeaways & Limitations
The main instantiation uses a minimal binary accept/reject model, and its distance-based evaluability metric is task-dependent.

Abstract

from arXiv · show

AI assistants often collaborate by proposing candidate edits, plans, or designs that users evaluate before adoption. Existing assistance methods focus on proposal quality or user-goal inference, often assuming that the user can reliably evaluate any proposal, which can fail in practice because of bounded rationality. We study evaluability-aware proposal planning, where proposals serve both as task interventions and as probes for learning latent preferences and evaluation constraints, where the resulting belief updates then guide later proposals. We formalise this setting as ProSE, a hidden-parameter sequential assistance problem, and instantiate it with a KL-regularised bounded-rational binary response model in which acceptance trades off value gain against a distance-dependent evaluability penalty. Analysing the planning consequence of this likelihood reveals that likely accepted proposals and informative probes need not coincide, which explains why planners that only pursue acceptance systematically underperform. We operationalise ProSE with \textsc{ProSE-Plan}, a depth-2 Bayes-adaptive planner that scores proposals by possible responses and response-induced posterior beliefs. In controlled graph simulations, \textsc{ProSE-Plan} improves over evaluability-unaware and myopic baselines when evaluation cost is the bottleneck, and a probe-commit ablation confirms that our approach selects informative proposals that simpler methods miss. Our results thus identify user evaluability as a planning-relevant dimension of AI assistance, complementary to generation quality and preference inference.

1 Introduction

Proposal-based assistance preserves user control by asking users to evaluate candidate next states, but effective planning must also account for whether proposals are evaluable. ProSE treats proposals as both interventions and probes, showing that informative responses can improve later assistance beyond immediate acceptance.

Motivation: Proposal-evaluation assistance lets users decide whether to incorporate suggested next states in coding, writing, and design tasks.The paradigm supports user control by proposing evaluable states rather than acting autonomously.
Motivation: Existing methods model user goals or uncertain action selection but largely neglect whether users can evaluate a proposal from the current state.Bounded cognitive and computational resources make large changes harder to inspect than smaller, potentially less optimal patches.
ProSE: ProSE gives each proposal a dual role as a task intervention and an observation probe for learning latent user parameters.The assistant uses responses both to predict proposal outcomes and to update beliefs guiding future choices.
ProSE: High-value proposals may be rejected when difficult to evaluate, whereas moderate proposals can produce responses that improve subsequent assistance.Planning must therefore account for response-induced changes in future proposal choice rather than immediate acceptance alone.
Contributions: The bounded-rational response model shows that likely-to-be-accepted proposals and informative probes need not coincide.Rejection can provide useful evidence about evaluability and support later proposal planning.
Contributions: PROSE-PLAN is a depth-2 Bayes-adaptive planner that scores proposals using possible responses and the posterior beliefs those responses induce.Controlled graph tasks evaluate end-to-end performance and response-dependent belief updates, identifying evaluability as complementary to generation quality and preference inference.

2 Preliminaries

The paper frames sequential assistance under latent uncertainty using Bayesian belief-state planning and models bounded rationality through KL-regularised decisions. This connects evolving beliefs about hidden parameters with users’ limited cognitive effort.

Bayesian decision-making: Bayesian decision-making represents sequential problems as MDPs with states, actions, transitions, rewards, and discounted expected return.The policy maps states to action distributions and plans over a finite horizon.
Bayesian decision-making: When transition or reward models contain latent parameters, the assistant maintains a posterior belief updated from interaction history and observed transitions.A prior over hidden parameters supports decisions that adapt as evidence accumulates.
Bayesian decision-making: A Bayes-adaptive MDP augments the state with the current belief, allowing future reward to be optimised under evolving model uncertainty.Its Q-values recursively evaluate actions with multiple steps of lookahead, using posterior beliefs after observations.
Information-theoretic bounded rationality: Information-theoretic bounded rationality models users as making decisions under cognitive and computational constraints rather than fully optimising without resource limits.The computational-rationality perspective treats deviations from perfect rationality as best use of limited cognitive resources under subjective utility.
Information-theoretic bounded rationality: The KL-regularised decision problem has a unique Gibbs-policy solution that tilts a default action distribution toward higher-utility actions according to inverse temperature κ.Larger κ produces more effortful deviation toward utility, while κ →0 recovers the default action.

3 Problem Setup: Proposal-based Sequential Assistance

ProSE models assistance as sequential proposal selection in which user responses determine state transitions while hidden user parameters remain uncertain. The resulting problem is a Bayes-adaptive MDP whose terminal reward is the user’s value of the final state.

Interaction model: The assistant proposes candidate next states or edits, the user evaluates them, and the realised state depends on the current state, proposal, and response.The assistant’s goal is to improve the final artefact through iterative proposals.
Interaction model: At each step, a proposal from C(s) elicits a response sampled from P(y | s, ˜s, z), after which response-dependent dynamics produce the next state.For design tasks, the transition is typically deterministic given the user’s response.
Bayes-adaptive formulation: ProSE is a Bayes-adaptive MDP whose transition model is defined by the user model and whose reward is zero except at the terminal state.The final reward is determined by the user value function Vϕ of the terminal state.
Bayes-adaptive formulation: The optimal Bayes-adaptive solution uses the user-defined terminal value as the last-step continuation value.This adapts the standard formulation by setting Q0 = Vϕ.

4 Bounded-Rational Binary User Response Model

The binary response model makes acceptance depend on both user-value gain and distance-based evaluability burden. Its acceptance and information frontiers show why the best probe may be expected to receive rejection, motivating response-dependent planning.

Binary response model: The binary model lets users accept or reject a proposal, transitioning to the proposed state on acceptance and leaving the current state unchanged on rejection.This minimal interaction captures common coding and writing interfaces while allowing evaluability to affect progress and learning.
Binary response model: Acceptance probability combines utility difference with a default-response term derived from a KL-regularised bounded-rational model.The utility difference equals the value gain between proposed and current states.
Evaluability penalty: The default response log-odds decrease with proposal distance, representing larger evaluation effort and a stronger default toward rejection.The distance transform g is non-decreasing with g(0) = 0 because evaluation difficulty need not scale proportionally with distance.
Evaluability penalty: The evaluability slope ρ shifts the acceptance threshold with distance, while κ controls how decisively responses reflect the value-cost difference.The latent parameters are z = (ϕ, ρ, κ), separating preference, evaluability, and response sharpness.
Planning implications: The frontiers imply that immediate acceptance and useful information are distinct planning considerations, making rejection potentially valuable evidence for future proposal choice.This motivates response-dependent belief updates rather than myopic acceptance maximisation.
Acceptance frontier: The acceptance frontier is defined by ∆Vϕ = ρ g(d), separating proposals more likely to be accepted from those more likely to be rejected.Farther proposals require larger value gains to remain acceptable.
Information frontier: Fisher information about ρ balances distance-dependent sensitivity against Bernoulli response variance, so information peaks at an intermediate distance.Very local proposals are insensitive to ρ, while very distant proposals are nearly always rejected and therefore weakly informative.
Information frontier: Under the stated regularity conditions, every global information maximiser lies where acceptance is less likely than rejection.For g(t) = t2, κ = 1, ρ = 0.5, and ∆Vϕ(t) = t, the information maximum lies beyond the acceptance frontier.

5 PROSE-PLAN: Evaluability-Aware Proposal Planning

PROSE-PLAN treats sequential assistance as Bayes-adaptive planning under latent user parameters. It uses response-dependent belief updates within a depth-2 lookahead to select proposals by their expected downstream value.

Planning formulation: PROSE-PLAN addresses ProSE as a Bayes-adaptive belief-state planning problem with latent user uncertainty.The framework can in principle use standard reinforcement-learning solutions once the response likelihood, transition model, and value family are specified.
Belief tracking: The planner tracks the posterior over z = (ϕ, ρ, κ) exactly on a finite parameter grid.More sophisticated Bayesian representations are noted as possible for larger parameter spaces.
Proposal selection: At depth 2, each candidate proposal is evaluated across possible responses, state transitions, and response-induced posterior beliefs.The second-step continuations are recomputed under each hypothetical updated belief.
Proposal selection: The proposal with the highest expected two-step value Q2 is selected.The final-step value is taken as an expectation over user preferences under the current hypothetical belief.
Computational cost: Exhaustive depth-2 evaluation costs O(|C|^2|Y|^2|Zgrid|) per planning step.This complexity uses maximum candidate-set size |C|, response-space size |Y|, and grid size |Zgrid|.

6 Experiments

The experiments test whether evaluability-aware planning improves finite-horizon proposal outcomes and whether its advantage comes from response-dependent belief updates. Across controlled graph tasks, PROSE-PLAN helps most when evaluation cost limits acceptance and probes can improve later decisions.

Experimental questions: The experiments evaluate end-to-end payoff and whether response-dependent belief updates, rather than lookahead alone, explain PROSE-PLAN’s gains.Q1 uses a branching-corridor task, while Q2 uses a probe-commit task.
Experimental setup: The tasks use finite graphs where proposals are candidate nodes, shortest-path distance represents evaluation difficulty, and rejection leaves the state unchanged.Acceptance moves the state to the proposed node, and episodes terminate on reaching the preferred goal or the horizon.
Branching-corridor task: The branching-corridor task tests the trade-off between easy generic progress and difficult personalised proposals.It uses a tree with a shared corridor, four branches, hidden preferred branch ϕ, and success defined as reaching the preferred leaf within the horizon.
End-to-end payoff: PROSE-PLAN reaches success 0.515 at αenv = 0.25 and ρtrue = 0.30, versus 0.215 for PERSONALISED-MYOPIC and 0.200 for POPULATION-MYOPIC.It degrades more gracefully as evaluation cost rises by selecting closer, more evaluable proposals.
Sensitivity to task structure: At high evaluation cost, PROSE-PLAN’s gain over the stronger myopic baseline is largest when αenv is small; at lower cost, the gain is consistently non-positive.When shared-corridor value is already sufficient or distant proposals remain evaluable, myopic methods become competitive.
Response-dependent lookahead: PROSE-PLAN reaches 0.815 success in probe-commit, compared with 0.550 for PERSONALISED-MYOPIC and 0.555 for BELIEF-FROZEN DEPTH-2.It probes in every episode, and response-dependent posterior updates improve success by 26 percentage points.

7 Discussion and Conclusion

The paper positions evaluability as a planning-relevant dimension of proposal-based assistance, alongside preference inference and proposal quality. It formalises responses as information about latent user parameters and identifies scope boundaries for the current instantiation.

Discussion and Conclusion: Evaluability is a distinct dimension of assistance because proposals must be valuable under user preferences and reliably evaluable from the current state.The paper treats each proposal as both a task intervention and an observation about the user.
Discussion and Conclusion: Likely accepted proposals and informative evaluability probes need not coincide, with the most informative proposals potentially lying on the expected-rejection side of the acceptance frontier.This coupling makes user responses relevant to both immediate proposal outcomes and future assistance.
Discussion and Conclusion: The main instantiation is limited to binary responses, task-dependent evaluability metrics, and a minimal depth-2 planner with exact grid inference.The authors identify richer response spaces, learned task-specific metrics, and scalable planning as future work.
Related Work: Prior work addresses hidden preferences, bounded rationality, query difficulty, and display timing, but evaluability-aware sequential proposal planning remains comparatively underexplored.The paper situates its contribution at the intersection of these research areas.
Discussion and Conclusion: PROSE-PLAN uses response-contingent Bayes-adaptive lookahead, updating beliefs over latent user parameters before evaluating follow-up proposals.This extends Bayes-adaptive planning by using the response model both to score proposals and to update beliefs hypothetically.

B.1 Derivation of the Gibbs policy

The paper derives a unique KL-regularised Gibbs policy by optimising a utility objective relative to a full-support prior. It then specialises this policy to binary acceptance and rejection responses with proposal-dependent evaluability costs.

Derivation of the Gibbs policy: Strict convexity of the KL term makes the objective strictly concave, so the maximising policy is unique.The prior has full support, ensuring finite KL divergence across the simplex.
Derivation of the Gibbs policy: The solution is a Gibbs policy that tilts the prior policy toward higher-utility actions by exp(κU(a)).The normalising factor ensures the tilted weights form a valid policy.
Derivation of the Gibbs policy: As the information-processing parameter vanishes, the bounded-rational policy remains at the prior policy.The default-policy limit follows directly from the Gibbs expression.
Binary response specialisation: For binary responses, acceptance probability is the normalised Gibbs weight for acceptance relative to the corresponding rejection weight.The binary response space is Y = {acc, rej}, with response utilities defined by the realised next state.
Binary response specialisation: Proposal-dependent evaluability is encoded through a monotone distance penalty, where d(s, ˜s) measures proposal distance and g(0) = 0.The penalty increases with the burden transform g as proposals move farther from the current state.

C.1 Information frontier conditional on user parameters

The analysis characterises how proposal distance affects information about evaluability under fixed latent user parameters. It shows that local Fisher information is distinct from Bayesian information gain, which the planner uses through posterior updates.

Information frontier: The ρ-Fisher information factors into squared distance sensitivity, g(t)^2, and Bernoulli response variance, p_z(t)(1 − p_z(t)).Information is therefore largest where distance affects the response and acceptance and rejection remain both plausible.
Boundary behaviour: At zero distance, g(0) = 0, making the local information about the evaluability slope vanish.Small-distance proposals are nearly insensitive to the evaluability slope.
Boundary behaviour: Under the stated tail condition, Fisher information tends to zero for sufficiently distant proposals, yielding an interior global maximiser.Continuity and the tail bound support existence of a maximum away from the current state.
Rejection-side characterisation: Every global information maximiser lies on the rejection side of the acceptance frontier, where p_z(t⋆) < 1/2.The proof excludes both positive logit values and the frontier itself as locations of a global maximum.
Bayesian information and planning: Mutual information measures belief change over the full latent parameter vector, whereas ρ-Fisher information is a narrower local diagnostic for sensitivity to ρ.The paper uses Fisher information for its closed-form distance analysis and mutual information for Bayesian information gain.
Bayes-adaptive planning: PROSE-PLAN uses hypothetical responses to update posterior beliefs before scoring follow-up proposals, unlike myopic baselines that omit downstream belief-update value.The experiments represent beliefs exactly on a finite grid after fixing the grid.

E.2.1 Full experimental setup

The Branching-Corridor environment tests assistance with hidden preference-specific goals in a finite tree containing a shared corridor and multiple branches. Episodes vary evaluation-cost and task-structure parameters under repeated random seeds.

Branching-Corridor task: Each episode samples a hidden preferred branch ϕ that determines the user’s goal state and state-value function.The assistant observes the realised current state and may propose any non-current node.
Branching-Corridor task: Acceptance moves the state to the proposed node, whereas rejection leaves the state unchanged.This response-mediated transition creates the task intervention evaluated by the planner.
Experimental conditions: The default high-cost condition uses αenv = 0.25, ρtrue = 0.30, and κtrue = 1.0.Main sweeps use 200 seeds per condition, while robustness and ablation checks use 50 seeds unless otherwise stated.

E.2.2 Additional Branching-Corridor Ablation

The belief-frozen depth-2 ablation shares PROSE-PLAN’s horizon but evaluates hypothetical continuations under the current belief rather than response-induced posteriors. In the Branching-Corridor environment, this ablation outperforms PROSE-PLAN, showing that the setting is not a clean isolation test for response-dependent lookahead.

Ablation design: The belief-frozen depth-2 ablation evaluates second-step continuations under the current belief rather than hypothetical response-induced posteriors.It still updates beliefs after observing real responses during execution.
Ablation result: Belief-frozen depth-2 outperforms PROSE-PLAN in the Branching-Corridor environment.The comparison uses the default high-cost condition αenv = 0.25, ρtrue = 0.30, and κtrue = 1.0 over 200 seeds.
Interpretation: The result indicates that Branching-Corridor is not a clean isolation test for response-dependent belief updates during lookahead.Branch proposals already produce informative real accept/reject outcomes during execution, making explicit valuation of hypothetical belief updates partly redundant.

E.2.3 Aggregate Proposal behaviour

At high evaluation cost, PROSE-PLAN separates from myopic baselines by avoiding maximal-distance jumps and using more evaluable proposals. Its proposal distances decrease across early steps while acceptance rates rise, supporting a value–evaluability trade-off rather than merely local progress.

Measures: The aggregate analysis reports mean proposal distance and empirical acceptance rate over episodes remaining active at each proposal step.These measures characterize how far planners propose and how often those proposals are accepted.
PROSE-PLAN: PROSE-PLAN’s mean proposal distance decreases from 4.00 at t = 0 to 2.05 at t = 3, while acceptance increases from 0.175 to 0.662.At the final step, distance rises again for more decisive proposals, but acceptance remains substantially above myopic baselines.
Interpretation: The behavior supports an interpretation in which PROSE-PLAN balances value gain against evaluability rather than improving solely through lower-value local moves.The figure caption likewise describes more evaluable intermediate proposals and higher acceptance rates than myopic baselines.

E.2.4 Representative Proposal Trajectories

Representative trajectories illustrate how evaluability-aware stepping stones and diagnostic probes support progress where direct commitments or conservative moves fail. Across the two task settings, PROSE-PLAN uses responses to update beliefs and select better subsequent proposals.

E.2.4 Representative Proposal Trajectories: In the default high-cost Branching-Corridor trajectory, VALUE-GREEDY and THRESHOLD remain in the shared corridor, while myopic planners make direct distant branch jumps.The trajectory uses αenv = 0.25, ρtrue = 0.30, κtrue = 1.0, and the same seed across methods.
E.2.4 Representative Proposal Trajectories: PROSE-PLAN uses an intermediate true-branch state b2-2 before committing to b2-4, reaching the preferred goal in two accepted steps.This exemplifies evaluable stepping-stone proposals instead of repeated long-distance jumps.
E.3.1 Full experimental setup: The Probe-Commit task makes probing useful only when the first response updates belief before the second proposal.Goals offer high immediate value but weak diagnosticity, whereas lower-value probes provide more informative responses about the hidden preference.
E.3.2 Sensitivity to Probe Diagnosticity: PROSE-PLAN probes only in the diagnostic regime: it does not probe at wp,− = −1 but probes in every episode for wp,− ≤ −2.More negative mismatched-probe values make wrong-branch probes easier to reject and responses more informative.
E.3.4 Illustrative Proposal Trajectories: In Probe-Commit, direct commitment to a wrong high-value goal can be accepted but leave correction as a long-distance proposal likely to be rejected.The resulting state change explains why both myopic planners can remain at the wrong goal and fail.
E.3.3 Belief Updates Induced by Probes: PROSE-PLAN instead uses a rejected wrong-branch probe to infer the preferred branch, then proposes the aligned goal from the start state.The probe response concentrates the posterior and guides the second-step commit.