Team Learning as a Game

Abstract

A machine FIN -learning machine M receives successive values of the function f it is learning; at some point M outputs conjecture which should be a correct index of f . When n machines simultaneously learn the same function f and at least k of these machines outut correct indices of f , we have team learning [ k, n ] FIN . Papers [DKV92, DK96] show that sometimes a team or a robabilistic learner can simulate another one, if its probability p (or team success ratio k/n ) is close enough. On the other hand, there are critical ratios which mae simulation o FIN ( p _2) by FIN ( p _1) imossible whenever p _2 _< r < p _1 or some critical ratio r . Accordingly to [DKV92] the critical ratio closest to 1/2 rom the let is 24/49; [DK96] rovides other unusual constants. These results are comlicated and rovide a ull icture o only or FIN - learners with success ratio above 12/25. We generalize [ k, n ] FIN teams to asymmetric teams [AFS97]. We introduce a two player game on two 0-1 matrices defining two asymmetric teams. The result of the game reflects the comparative power of these asymmetric teams. Hereby we show that the problem to determine whether [ k _1] FIN ⊂ [ k _2, n _2] FIN is algorithmically solvable. We also show that the set of all critical ratios is well-ordered. Simulating asymmetric teams with probabilistic machines from [AFS97] provides some insight about the unusual constants like 24/49.