Saturday, June 21, 2008

Making choices: adaptive strategy

We revisit the problem of selecting one among N candidates based on the evaluation of M independent normally distributed random candidate traits, with the constraint that at most N traits (out of the total NM) can be evaluated: our goal is to improve the simple and two-stage strategies we had previously analyzed.

The idea behind an adaptive strategy is to make at each step the decision that maximizes the expected result given the information obtained so far. We study this approach for a simplified scenario: suppose we have only three candidates c1, c2, c3 with (unkown to the strategy) scores s1, s2, s3 and current partial scores (known to the strategy) s'1 > s'2 > s'3, respectively. In this situation, the best strategy is to choose c1, and the average result is precisely s'1, since s1s'1 is a normal distribution with mean value 0. Now, if we are allowed to evaluate one more trait, and the three candidates have still unevaluated traits, how to best spend this extra resource? Let us examine the result for each possible decision:

Evaluate c1. Let us call t1 the newly evaluated trait of c1. If s'1 + t1 > s'2, we stick to c1; otherwise, we change our selection to c2. The average score we obtain can then be calculated as

S1 = (s'1 + E(t1 | t1 > s'2s'1))·P(t1 > s'2s'1) + s2·P(t1 < s'2s'1),

where t1 follows a normal distribution with mean 0 and variance 1. Note that the unevaluated traits do not affect the expected score because their mean is 0.

Evaluate c2. If we call t2 the extra trait evaluated for c2, the analysis is similar to that of the previous case and yields

S2 = s'1·P(t2 < s'1s'2) + (s'2 + E(t2 | t2 > s'1s'2))·P(t2 > s'1s'2).

Using the fact that the statistical distribution of t2 is identical to that of t1 and the symmetry of this distribution around 0, elementary manipulations on the expressions above lead us to conclude that

S1 = S2.

Evaluate c3. Calling t3 the extra trait evaluated for c3, we have

S3 = s'1·P(t3 < s'1s'3) + (s'3 + E(t3 | t3 > s'1s'3))·P(t3 > s'1s'3).

Again, t3 has the same statistical distribution as t2; but since s'3 < s'2 it is not hard to prove that

S3 < S2.

So, the most efficient way to spend the extra trait evaluation is using it with either c1 or c2. This result readily extends to the general case:

adaptive strategy(c1,...,cN)
{s holds the partial scores of c1,...,cN}
s ← {0,...0}
i = 1 to N
····select some cj with unevaluated traits and maximum sj
····evaluate new trait t on cj
····sjsj + t
end for
select a candidate ck with maximum sk

This extremely simple strategy has been implemented in C++ (Boost is needed to compile the program) and exercised for the same settings as in previous cases, N = 60, M = 5. The figure shows the performance of the adaptive strategy compared with the best simple and two-stage strategies and the optimum case (which is not attainable as it requires knowledge of all the NM traits of the candidate pool):

Note that we have not proved that this adaptive strategy is optimum, i.e. a strategy with the best possible expected score. That would be the case if the following optimal substructure property held true: if S is an optimum strategy for n evaluation traits and a strategy S' is identical to S except in that it omits the last trait evaluation, then S' is an optimum strategy for n − 1 evaluation traits.

No comments :

Post a Comment