The broad setting where our work is placed is when there are one or more edge servers which assist clients in carrying out computation tasks and the goal is to determine which tasks to offload to the edge server(s) so that the overall cost is minimized. One approach towards the design of such schemes is to formulate the problem as a large-scale one-shot optimization problem [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}. While solving the problem exactly turns out to be NP-hard in several instances, efficient heuristics are presented. Recently, [7]} studied the impact of decentralization on the performance of such task offloading schemes. Finally, [9]} used a game-theoretic approach to study the problem by considering a two-stage interactive game between an edge server and the users, wherein the server announces prices for hosting various services in the first stage and each user independently makes its offloading decision in the second round. Our work differs from this line of work in that we design online algorithms which adapt their service placement decisions dynamically over time depending on the varying number of requests and rental costs.
