Adaptive load-balancing strategies for distributed systems

Describes SMALL, a system for learning load-balancing strategies in distributed computer systems. The load balancing problem is an ill-posed optimization problem because its objective function is ill-defined. Realistic state-space representations of this problem do not satisfy the Markov property. Experimentally feasible learning environments for load balancing exhibit delayed, evaluative feedback. Such aspects complicate the learning of strategies for load balancing. SMALL uses comparator neural networks for learning to compare objective-function values of states resulting from a set of alternative moves. The problem of learning from delayed evaluative feedback, also called the credit-assignment problem of reinforcement learning, is solved only for Markovian problems. The paper presents a novel credit-assignment procedure suitable for load balancing and other non-Markovian learning tasks