Capabilities of probabilistic learners with bounded mind changes
Robert Daley, Bala Kalyanasundaram · 1993
We consider the power of randomization in finite learning when a bounded number of mind changes are allowed.We show that in the ~m+2_3 range ( ~~+a _2, 1] the capability type of probabilistic as well as pluralistic FIN-type (also PFIN-type) learners is defined by the sequence 2"'+7-3 n+l {w n ~O}, where m ~O is the allowed number of mind changes for the learners.This generalizes most of the results known in the literature on finite learning.For any fixed number of mind changes, we show that deterministic strategies can simulate probabilistic strategies where the success ratio is close to but not equal to 1. F'inaHy, our results demonstrate the power of redundancy when a bounded number of mind changes are allowed.In contrast, it is known that the power of redundancy disappears when an apriori unbounded (but finite) number of mind changes are allowed.