  We learn optimal user association policies for traffic from different
locations to Access Points(APs), in the presence of unknown dynamic traffic
demand. We aim at minimizing a broad family of $\alpha$-fair cost functions
that express various objectives in load assignment in the wireless downlink,
such as total load or total delay minimization. Finding an optimal user
association policy in dynamic environments is challenging because traffic
demand fluctuations over time are non-stationary and difficult to characterize
statistically, which obstructs the computation of cost-efficient associations.
Assuming arbitrary traffic patterns over time, we formulate the problem of
online learning of optimal user association policies using the Online Convex
Optimization (OCO) framework. We introduce a periodic benchmark for OCO
problems that generalizes state-of-the-art benchmarks. We exploit inherent
properties of the online user association problem and propose PerOnE, a simple
online learning scheme that dynamically adapts the association policy to
arbitrary traffic demand variations. We compare PerOnE against our periodic
benchmark and prove that it enjoys the no-regret property, with additional
sublinear dependence of the network size. To the best of our knowledge, this is
the first work that introduces a periodic benchmark for OCO problems and a
no-regret algorithm for the online user association problem. Our theoretical
findings are validated through results on a real-trace dataset.
