Feasibility optimality of periodwise static priority policies for a quality of service model in wireless networks and convergence analysis for an online recommendation system

摘要

In the first part of this thesis, we consider a proposed Quality of Service(QoS) model in which a set of clients require their own timely-throughputfrom an access point, with packet deadlines restricted to be in one period. It isknown that two debt-based policies, including time-based debt and weighteddelivery-based debt, are feasibility optimal in the sense that they can fulfillthe requirements of all sets of feasible clients. We analyze why these poli-cies are optimal by considering a class of periodwise static priority policies.We prove that this latter class of policies can achieve whatever a history-dependent policy can, i.e., it suffices to consider only this class of policiesfor such a scheduling problem. Our approach proceeds by investigating thesubmodularity of the complement of the idle time function. We thereby showthat the set defined by the timely-throughput constraints is a polymatroid,from which the optimality within the class of periodwise static priority poli-cies follows.The second part of the thesis analyzes the convergence of an algorithmfor the problem of learning with expert advice. At the present time, severalweb-based recommendation systems use votes from experts or other users torecommend objects to other customers. We apply the `learning from expertadvice' framework for this system, and propose a recommendation algorithmthat uses a weighted update rule. Often, recommendation algorithms makeassumptions that do not hold in practice, such as requiring a large number ofgood objects, presence of experts with the identical taste as the user receivingthe recommendation, or experts who vote on all or a majority of objects. Ouralgorithm relaxes these assumptions by allowing an arbitrary proportion ofbad objects as well as arbitrary tastes of experts. Moreover, it can deal withthe issues that arise because of the existence of sleeping-experts, i.e., expertswho are not available for voting at all rounds. A key attribute of our approachis to define the concept of the best expert on the basis of both availabilityand accuracy of experts. We then prove that the algorithm converges almostsurely to the best expert(s) regardless of whether the predictions of expertsare binary or continuous valued. Moreover, we derive an upper bound onloss of the proposed algorithm by comparing it to the loss of an appropriatelydefined `current best' and show that the regret of our algorithm is logarithmicin the number of experts. Besides theoretical performance guarantees, wepresent simulation results that show the proposed algorithm outperformsDsybil, the current state-of-the-art recommendation algorithm.