A Hierarchy of Twofold Resource Allocation Automata Supporting Optimal Sampling

Abstract

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.