A Hierarchy of Twofold Resource Allocation Automata Supporting Optimal Sampling.

We consider the problem of allocating limited sampling resources in a ˵real-time″ manner with the purpose of estimating multiple binomial proportions. More specifically, the user is presented with `n΄ sets of data points, S₁, S₂, ..., S_n, where the set S_i has N_i points drawn from two classes {ω₁, ω₂}. A random sample in set S_i belongs to ω₁ with probability u_i and to ω₂ with probability 1 − u_i, with {u_i}. i = 1, 2, ...n, being the quantities to be learnt. The problem is both interesting and non-trivial because while both n and each N_i are large, the number of samples that can be drawn is bounded by a constant, c. We solve the problem by first modelling it as a Stochastic Non-linear Fractional Knapsack Problem. We then present a completely new on-line Learning Automata (LA) system, namely, the Hierarchy of Twofold Resource Allocation Automata (H-TRAA), whose primitive component is a Twofold Resource Allocation Automaton (TRAA), both of which are asymptotically optimal. Furthermore, we demonstrate empirically that the H-TRAA provides orders of magnitude faster convergence compared to the LAKG which represents the state-of-the-art. Finally, in contrast to the LAKG, the H-TRAA scales sub-linearly. Based on these results, we believe that the H-TRAA has also tremendous potential to handle demanding real-world applications. [ABSTRACT FROM AUTHOR]