Learning-based Decision-making under Stochastic and Adversarial Uncertainties

Abstract

This thesis studies two online learning problems in which the efficiency of the proposed strategies is studied in terms of their regret. The first problem deals with designing learning algorithms that optimize the social welfare of a single server queuing system when both the arrival and service rates are unknown and the second one involves finding an asymptotically optimal strategy for the problem of prediction with expert advice.

In Chapter II, we consider a long-term average profit maximizing admission control problem in an M/M/1 queuing system with unknown service and arrival rates. We propose a learning-based dispatching algorithm and characterize its regret with respect to optimal threshold dispatch policies. We show that our algorithm achieves O(1) regret when feasible, and O(ln1+ε(N)) otherwise for every ε > 0 where N is the number of customers arrived.

In Chapter III, we consider the problem of prediction with expert advice under the adversarial setting with a geometric stopping time from a zero-sum game point of view. In the literature, it has been shown in this setting that the discounted cost problem yields the solution of the long-term average cost problem as the discount parameter goes to 0, when quantities are appropriately scaled. We will focus on this asymptotic regime, and hence, the long-term average behavior of this game. We show that it is optimal for nature to play the “comb strategies” in the 4 expert game and that the best regret grows as O(1/ √2δ), where δ is the parameter of the geometric stopping time.