Online learning for network optimization under unknown models

Author

Yixuan Zhai ; Qing Zhao

Author_Institution

Electr. & Comput. Eng., Univ. of California, Davis, Davis, CA, USA

fYear

2013

fDate

3-5 Dec. 2013

Firstpage

575

Lastpage

578

Abstract

We consider the shortest path problem in a communication network with random link costs drawn from unknown distributions. A realization of the total end-to-end cost is obtained when a path is selected for communication. The objective is an online learning algorithm that minimizes the total expected communication cost in the long run. The problem is formulated as a multi-armed bandit problem with dependent arms, and an algorithm based on basis-based learning integrated with a Best Linear Unbiased Estimator (BLUE) is developed.

Keywords

learning (artificial intelligence); random processes; telecommunication computing; telecommunication links; telecommunication network routing; BLUE; basis-based learning; best linear unbiased estimator; communication network; multiarmed bandit problem; multihop communication network; network optimization; online learning algorithm; packet routing; random link costs; shortest path problem; total end-to-end cost; total expected communication cost; unknown distribution model; Adaptation models; Cognitive radio; Delays; Optimization; Random variables; Routing; Vectors; Bandit problem; best linear unbiased estimator; shortest path;

fLanguage

English

Publisher

ieee

Conference_Titel

Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE

Conference_Location

Austin, TX

Type

conf

DOI

10.1109/GlobalSIP.2013.6736943

Filename

6736943