This paper studies an online optimal resource reservation problem in
communication networks with job transfers where the goal is to minimize the
reservation cost while maintaining the blocking cost under a certain budget
limit. To tackle this problem, we propose a novel algorithm based on a
randomized exponentially weighted method that encompasses long-term
constraints. We then analyze the performance of our algorithm by establishing
an upper bound for the associated regret and the cumulative constraint
violations. Finally, we present numerical experiments where we compare the
performance of our algorithm with those of reinforcement learning where we show
that our algorithm surpasses it.

本论文研究了在具有作业转移的通信网络中的在线最优资源预留问题，目标是在一定预算限制下最小化预留成本并保持阻塞成本。我们提出了一种基于随机指数加权方法的新算法，可以处理长期约束。通过建立相关遗憾和累积约束违反的上界，我们分析了我们算法的性能。最后，我们通过数值实验证明了我们的算法与强化学习算法相比的性能优势。

在线网络资源分配的指数加权算法与长期约束

Exponentially Weighted Algorithm for Online Network Resource Allocation  with Long-Term Constraints

We tackle in this paper an online network resource allocation problem with
job transfers. The network is composed of many servers connected by
communication links. The system operates in discrete time; at each time slot,
the administrator reserves resources at servers for future job requests, and a
cost is incurred for the reservations made. Then, after receptions, the jobs
may be transferred between the servers to best accommodate the demands. This
incurs an additional transport cost. Finally, if a job request cannot be
satisfied, there is a violation that engenders a cost to pay for the blocked
job. We propose a randomized online algorithm based on the exponentially
weighted method. We prove that our algorithm enjoys a sub-linear in time
regret, which indicates that the algorithm is adapting and learning from its
experiences and is becoming more efficient in its decision-making as it
accumulates more data. Moreover, we test the performance of our algorithm on
artificial data and compare it against a reinforcement learning method where we
show that our proposed method outperforms the latter.

我们在本文中解决了一种带有任务转移的在线网络资源分配问题，提出了基于指数加权方法的随机在线算法，证明了该算法具有次线性时间后悔，通过对人工数据进行性能测试并与强化学习方法进行比较表明我们的方法优于后者。