We consider the problem of efficiently routing jobs that arrive into a
central queue to a system of heterogeneous servers. Unlike homogeneous systems,
a threshold policy, that routes jobs to the slow server(s) when the queue
length exceeds a certain threshold, is known to be optimal for the
one-fast-one-slow two-server system. But an optimal policy for the multi-server
system is unknown and non-trivial to find. While Reinforcement Learning (RL)
has been recognized to have great potential for learning policies in such
cases, our problem has an exponentially large state space size, rendering
standard RL inefficient. In this work, we propose ACHQ, an efficient policy
gradient based algorithm with a low dimensional soft threshold policy
parameterization that leverages the underlying queueing structure. We provide
stationary-point convergence guarantees for the general case and despite the
low-dimensional parameterization prove that ACHQ converges to an approximate
global optimum for the special case of two servers. Simulations demonstrate an
improvement in expected response time of up to ~30% over the greedy policy that
routes to the fastest available server.

我们提出了一种基于低维度软阈值策略参数化的高效策略梯度算法 ACHQ，利用底层排队结构，针对中心队列向异构服务器系统中任务迅速路由的问题。我们为一般情况提供了静态点收敛保证，并且尽管参数化维度较低，但证明了 ACHQ 对于两个服务器的特殊情况收敛于近似全局最优解。模拟结果表明，与贪婪策略相比，ACHQ 在预期响应时间上提高了约 30%。

异构排队系统作业路由的高效强化学习

Efficient Reinforcement Learning for Routing Jobs in Heterogeneous  Queueing Systems

This paper addresses a fundamental limitation for the adoption of caching for
wireless access networks due to small population sizes. This shortcoming is due
to two main challenges: (i) making timely estimates of varying content
popularity and (ii) inferring popular content from small samples. We propose a
framework which alleviates such limitations.
To timely estimate varying popularity in a context of a single cache we
propose an Age-Based Threshold (ABT) policy which caches all contents requested
more times than a threshold $\widetilde N(\tau)$, where $\tau$ is the content
age. We show that ABT is asymptotically hit rate optimal in the many contents
regime, which allows us to obtain the first characterization of the optimal
performance of a caching system in a dynamic context. We then address small
sample sizes focusing on $L$ local caches and one global cache. On the one hand
we show that the global cache learns L times faster by aggregating all requests
from local caches, which improves hit rates. On the other hand, aggregation
washes out local characteristics of correlated traffic which penalizes hit
rate. This motivates coordination mechanisms which combine global learning of
popularity scores in clusters and LRU with prefetching.

本研究讨论了无线接入网络中缓存应用的困境，提出了一种缓解局限性的框架，其中包括基于年龄阈值策略的缓存，以及局部和全局缓存之间的协调机制。

将动态内容放置在小容量缓存中

Placing Dynamic Content in Caches with Small Population

The smart power grid aims at harnessing information and communication
technologies to enhance reliability and enforce sensible use of energy. Its
realization is geared by the fundamental goal of effective management of demand
load. In this work, we envision a scenario with real-time communication between
the operator and consumers. The grid operator controller receives requests for
power demands from consumers, with different power requirement, duration, and a
deadline by which it is to be completed. The objective is to devise a power
demand task scheduling policy that minimizes the grid operational cost over a
time horizon. The operational cost is a convex function of instantaneous power
consumption and reflects the fact that each additional unit of power needed to
serve demands is more expensive as demand load increases.First, we study the
off-line demand scheduling problem, where parameters are fixed and known. Next,
we devise a stochastic model for the case when demands are generated
continually and scheduling decisions are taken online and focus on long-term
average cost. We present two instances of power consumption control based on
observing current consumption. First, the controller may choose to serve a new
demand request upon arrival or to postpone it to the end of its deadline.
Second, the additional option exists to activate one of the postponed demands
when an active demand terminates. For both instances, the optimal policies are
threshold based. We derive a lower performance bound over all policies, which
is asymptotically tight as deadlines increase. We propose the Controlled
Release threshold policy and prove it is asymptotically optimal. The policy
activates a new demand request if the current power consumption is less than a
threshold, otherwise it is queued. Queued demands are scheduled when their
deadline expires or when the consumption drops below the threshold.

设计了一种阈值策略的调度算法和理论界限，应用于实时通信的智能电网中的电力需求调度问题，基于随机模型并考虑长期平均成本。