Two-time scale learning automata: an efficient decision making mechanism for stochastic nonlinear resource allocation

摘要

The Stochastic Non-linear Fractional Equality Knapsack (NFEK) problem is a substantial resource allocation problem which admits a large set of applications such as web polling under polling constraints, and constrained estimation. The NFEK problem is usually solved by trial and error based on noisy feedback information from the environment. The available solutions to NFEK are based on the traditional family of Reward-Inaction Learning Automata (LA) scheme where the action probabilities are updated based on only the last feedback. Such an update form seems counterproductive for two reasons: 1) it only uses the last feedback and does not consider the whole history of the feedback and 2) it ignores updates whenever the last feedback does not correspond to a reward. In this paper, we rather suggest instead a learning solution that resorts to the whole history of feedback using the theory of two time-scale separation. Through comprehensive experimental results we show that the proposed solution is not only superior to the state-of-the-art in terms of peak performance but is also robust to the choice of the tuning parameters.