  In this paper, we study scheduling of a queueing system with zero knowledge
of instantaneous network conditions. We consider a one-hop single-server
queueing system consisting of $K$ queues, each with time-varying and
non-stationary arrival and service rates. Our scheduling approach builds on an
innovative combination of adversarial bandit learning and Lyapunov drift
minimization, without knowledge of the instantaneous network state (the arrival
and service rates) of each queue. We then present two novel algorithms
\texttt{SoftMW} (SoftMaxWeight) and \texttt{SSMW} (Sliding-window
SoftMaxWeight), both capable of stabilizing systems that can be stablized by
some (possibly unknown) sequence of randomized policies whose time-variation
satisfies a mild condition. We further generalize our results to the setting
where arrivals and departures only have bounded moments instead of being
deterministically bounded and propose \texttt{SoftMW+} and \texttt{SSMW+} that
are capable of stabilizing the system. As a building block of our new
algorithms, we also extend the classical \texttt{EXP3.S} (Auer et al., 2002)
algorithm for multi-armed bandits to handle unboundedly large feedback signals,
which can be of independent interest.
