Expected-Utility Plan Selection

The problem, from first principles

Often an agent has several candidate plans: a quick one that works 60% of the time, a thorough one that works 95% of the time but costs ten times as much. Choosing between them is decision-making under uncertainty, and the right yardstick is expected utility: the probability of success times the value of success, minus a weighted cost. Retries change the picture. If an attempt costs c and succeeds with probability p, trying up to n times raises the overall success probability to 1 - (1 - p)^n, but you only pay for later attempts when earlier ones failed. A cheap unreliable plan with retries can beat an expensive reliable one.

From theory to code

Implement success_after_retries, expected_attempt_cost and select_plan.

Constraints

• success_after_retries(p, n) is 1 - (1 - p) ** n.
• expected_attempt_cost(p, cost, n) is the expected total cost of up to n sequential attempts, paying cost for each attempt that is actually made: cost * sum_{k=0}^{n-1} (1 - p) ** k.
• select_plan(plans, cost_weight): each plan is a dict with p, value, cost and attempts. Its utility is value * success_after_retries(p, attempts) - cost_weight * expected_attempt_cost(p, cost, attempts). Return the index of the plan with the highest utility (lowest index on ties).

Hints