The reinforcement learning paradigm has been shown to be an effective approach in solving the k-server problem. However, this approach is based on the Q-learning algorithm, being subjected to the curse of dimensionality problem, since the action-value function (Q-function) grows exponentially with the increase in the number of states and actions. In this work, a new algorithm based on the deep reinforcement learning paradigm is proposed. For this, the Q-function is defined by a multilayer perceptron neural network that extracts the information of the environment from images that encode the dynamics of the problem. The applicability of the proposed algorithm is illustrated in a case study in which different nodes and servers problem configurations are considered. The agents behavior is analyzed during the training phase and its efficiency is evaluated from performance tests that quantify the quality of the generated server displacement policies. The results obtained provide a new algorithm promising view as an alternative solution to the k-server problem.

Introduction

In online computation a computer algorithm must decide how to act from the currently available input, without being aware of the entire set of inputs (Allan & El-Yaniv, 1998). Several current issues can be inserted in this type of problem, for example, given the price of Bitcoin, must the crypto currency be sold or bought? How to assign and reassign processes in a parallel processing so that there is load balancing on all processors? How to move a facility into an online transportation service minimizing the total cost involved in the process? Problems like these are complex since after a decision is made, it cannot be revoked, influencing the solution as a whole. Proposed by Manasse, McGeoch, and Sleator (1988) the k-server problem (KSP) is the problem of moving k servers over n nodes on a graph (or metric space) in order to satisfy the requests that appear online (sequentially) minimizing some cost function determined by the problem. Its conceptual simplicity contrasts with its complexity that grows exponentially with the increase in number of nodes and servers, being perhaps the most influential online problem, serving as a propeller for the development of new algorithms (Bansal, Buchbinder, Madry, & Naor, 2015; Gupta, Kamali, & López-Ortiz, 2016). Initially, the works related to the k-server problem focused on special metric spaces such as the uniform metric space, which corresponds to the paging problem in which high-performance algorithms are known (Sleator & Tarjan, 1985). For general metrics, Koutsoupias (2009) proposed the work function algorithm which is suitable for any metric space, obtaining results close to optimal solutions.