  In this paper, a new structure of cooperative learning automata so-called
extended learning automata (eDLA) is introduced. Based on the proposed
structure, a new iterative randomized heuristic algorithm for finding optimal
sub-graph in a stochastic edge-weighted graph through sampling is proposed. It
has been shown that the proposed algorithm based on new networked-structure can
be to solve the optimization problems on stochastic graph through less number
of sampling in compare to standard sampling. Stochastic graphs are graphs in
which the edges have an unknown distribution probability weights. Proposed
algorithm uses an eDLA to find a policy that leads to an induced sub-graph that
satisfies some restrictions such as minimum or maximum weight (length). At each
stage of the proposed algorithm, eDLA determines which edges to be sampled.
This eDLA-based proposed sampling method may result in decreasing unnecessary
samples and hence decreasing the time that algorithm requires for finding the
optimal sub-graph. It has been shown that proposed method converge to optimal
solution, furthermore the probability of this convergence can be made
arbitrarily close to 1 by using a sufficiently small learning rate. A new
variance-aware threshold value was proposed that can be improving significantly
convergence rate of the proposed eDLA-based algorithm. It has been shown that
the proposed algorithm is competitive in terms of the quality of the solution
