Problems of adaptive optimization in multiclass M/GI/1 queues with Bernoulli feedback

Adaptive algorithms are obtained for the solution of separable optimization problems in multiclass M/GI/1 queues with Bernoulli feedback. Optimality of the algorithms is established by modifying and extending methods of stochastic approximation. These algorithms can be used as a basis for designing policies for semi-separable and approximate lexicographic optimization problems and in the case of M/GI/1 queues without feedback, they also provide a simple policy for lexicographic optimization. The results obtained on stochastic approximation imply convergence of classical recursions such as Robbins–Monroe in cases where the conditional second moment of their increments is not finite.