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 c_{1}, c_{2}, c_{3} with (unkown to the strategy) scores s_{1}, s_{2}, s_{3} and current partial scores (known to the strategy) s'_{1} > s'_{2} > s'_{3}, respectively. In this situation, the best strategy is to choose c_{1}, and the average result is precisely s'_{1}, since s_{1} − s'_{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 c_{1}. Let us call t_{1} the newly evaluated trait of c_{1}. If s'_{1} + t_{1} > s'_{2}, we stick to c_{1}; otherwise, we change our selection to c_{2}. The average score we obtain can then be calculated as

S_{1} = (s'_{1} + E(t_{1} | t_{1} > s'_{2} − s'_{1}))·P(t_{1} > s'_{2} − s'_{1}) + s_{2}·P(t_{1} < s'_{2} − s'_{1}),

where t_{1} 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 c_{2}. If we call t_{2} the extra trait evaluated for c_{2}, the analysis is similar to that of the previous case and yields

S_{2} = s'_{1}·P(t_{2} < s'_{1} − s'_{2}) + (s'_{2} + E(t_{2} | t_{2} > s'_{1} − s'_{2}))·P(t_{2} > s'_{1} − s'_{2}).

Using the fact that the statistical distribution of t_{2} is identical to that of t_{1} and the symmetry of this distribution around 0, elementary manipulations on the expressions above lead us to conclude that

S_{1} = S_{2}.

Evaluate c_{3}. Calling t_{3} the extra trait evaluated for c_{3}, we have

S_{3} = s'_{1}·P(t_{3} < s'_{1} − s'_{3}) + (s'_{3} + E(t_{3} | t_{3} > s'_{1} − s'_{3}))·P(t_{3} > s'_{1} − s'_{3}).

Again, t_{3} has the same statistical distribution as t_{2}; but since s'_{3} < s'_{2} it is not hard to prove that

S_{3} < S_{2}.

So, the most efficient way to spend the extra trait evaluation is using it with either c_{1} or c_{2}. This result readily extends to the general case:

adaptive strategy(c_{1},...,c_{N})

{s holds the partial scores of c_{1},...,c_{N}}

s ← {0,...0}

for i = 1 to N

····select some c_{j} with unevaluated traits and maximum s_{j}

····evaluate new trait t on c_{j}

····s_{j} ← s_{j} + t

end for

select a candidate c_{k} with maximum s_{k}

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