How do I optimize this scenario to achieve the lowest score?

Question

Here is the scenario:

I am iteratively seeking a goal state by selecting from one of a set of sets of options. The set of sets defines the possible routes to the goal state, and each inner set defines the probability I will succeed, and what the failure penalties and probabilities are. A failure costs me a variable amount of score, which is also a given.

My objective is not only to achieve the goal state, but to do so with minimum score.

For example, say I can select from two groups:

In group 1, I have a 25% chance of success. However, I have a 50% chance of failing and adding 5 to my score, and a 25% chance of failing and adding 10 to my score.

In group 2, I have a 50% chance of success. However, I have a 10% chance of failing and adding 5 to my score, a 30% chance of failing and adding 15 to my score, and a 10% chance of failing and adding 25 to my score.

If I wish to succeed while minimizing my score, which of these two groups should I repeatedly select from?

I'm looking for a general solution to this problem, where there may be an arbitrary number of groups, and each group has an arbitrary number of outcomes. As in the example, for each group, their relative probabilities of success and failure are known, along with the points added for failing.

I think I want to optimize for "mean score for success" in the group in order to minimize my overall score. However, I'm a bit confused because it seems to me that if the distribution of possible final scores is flat enough, I may be better off accepting a higher mean score from my selected group.

Answer 1

If we're talking minimize expected score, you are in effect comparing a multiple of the means of two geometric distributions.

In each case you keep failing until you succeed, with constant probability of success, and the number of rounds you fail before you succeed determines the expected score.

http://en.wikipedia.org/wiki/Geometric_distribution

For group 1, when you fail, you add on average $\frac{0.5\times 5+0.25\times 10}{0.5+0.25}=\frac{20}{3}$ to the score.

For group 2, when you fail, you add on average $\frac{0.1\times 5+0.3\times 15+0.1\times 25}{0.1+0.3+0.1}=15$ to the score.

For group 1, on average you fail $\frac{1-p_1}{p_1} = \frac{.75}{.25} = 3$ times before you succeed.

For group 2, on average you fail $\frac{1-p_2}{p_2} = \frac{.5}{.5} = 1$ times before you succeed.

So your expected score at success for group 1 is 20.

Your expected score at success for group 2 is 15.

Similar calculations can be done for other setups.