Extended distributed learning automata An automata-based framework for solving stochastic graph optimization problems

Abstract In this paper, a new structure for coopera-tive learning automata called extended learning automata (eDLA) is introduced. Based on the new structure, an iterative randomized heuristic algorithm using sampling is proposed for finding an optimal subgraph in a stochastic edge-weighted graph. Stochastic graphs are graphs in which the weights of edges have an unknown probability distri-bution. The proposed algorithm uses an eDLA to find a policy that leads to a subgraph that satisfy some restric-tions such as minimum or maximum weight (length). At each stage of the proposed algorithm, the eDLA determines which edges should be sampled. The proposed eDLA-based sampling method may reduce unnecessary samples and hence decrease the time required for finding an optimal sub-graph. It is shown that the proposed method converges to an optimal solution, the probability of which can be made arbitrarily close to 1 by using a sufficiently small learn-ing parameter. A new variance-aware threshold value is also proposed that can significantly improve the convergence rate of the proposed eDLA-based algorithm. It is further shown that our algorithm is competitive in terms of the quality of the solution