  The present paper deals with online convex optimization involving both
time-varying loss functions, and time-varying constraints. The loss functions
are not fully accessible to the learner, and instead only the function values
(a.k.a. bandit feedback) are revealed at queried points. The constraints are
revealed after making decisions, and can be instantaneously violated, yet they
must be satisfied in the long term. This setting fits nicely the emerging
online network tasks such as fog computing in the Internet-of-Things (IoT),
where online decisions must flexibly adapt to the changing user preferences
(loss functions), and the temporally unpredictable availability of resources
(constraints). Tailored for such human-in-the-loop systems where the loss
functions are hard to model, a family of bandit online saddle-point (BanSaP)
schemes are developed, which adaptively adjust the online operations based on
(possibly multiple) bandit feedback of the loss functions, and the changing
environment. Performance here is assessed by: i) dynamic regret that
generalizes the widely used static regret; and, ii) fit that captures the
accumulated amount of constraint violations. Specifically, BanSaP is proved to
simultaneously yield sub-linear dynamic regret and fit, provided that the best
dynamic solutions vary slowly over time. Numerical tests in fog computation
offloading tasks corroborate that our proposed BanSaP approach offers
competitive performance relative to existing approaches that are based on
gradient feedback.
