Max weight learning algorithms for scheduling in unknown environments

Michael J. Neely; Scott T. Rager; Thomas F. La Porta

doi:10.1109/TAC.2012.2191874

Max weight learning algorithms for scheduling in unknown environments

Michael J. Neely, Scott T. Rager, Thomas F. La Porta

Research output: Contribution to journal › Article › peer-review

28 Scopus citations

Abstract

We consider a discrete time queueing system where a controller makes a 2-stage decision every slot. The decision at the first stage reveals a hidden source of randomness with a control-dependent (but unknown) probability distribution. The decision at the second stage generates an attribute vector that depends on this revealed randomness. The goal is to stabilize all queues and optimize a utility function of time average attributes, subject to an additional set of time average constraints. This setting fits a wide class of stochastic optimization problems, including multi-user wireless scheduling with dynamic channel measurement decisions, and wireless multi-hop routing with multi-receiver diversity and opportunistic routing decisions. We develop a simple max-weight algorithm that learns efficient behavior by averaging functionals of previous outcomes.

Original language	English (US)
Article number	6174451
Pages (from-to)	1179-1191
Number of pages	13
Journal	IEEE Transactions on Automatic Control
Volume	57
Issue number	5
DOIs	https://doi.org/10.1109/TAC.2012.2191874
State	Published - May 2012

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/TAC.2012.2191874

Cite this

@article{dc265cc09819493cbb97244207b53360,

title = "Max weight learning algorithms for scheduling in unknown environments",

abstract = "We consider a discrete time queueing system where a controller makes a 2-stage decision every slot. The decision at the first stage reveals a hidden source of randomness with a control-dependent (but unknown) probability distribution. The decision at the second stage generates an attribute vector that depends on this revealed randomness. The goal is to stabilize all queues and optimize a utility function of time average attributes, subject to an additional set of time average constraints. This setting fits a wide class of stochastic optimization problems, including multi-user wireless scheduling with dynamic channel measurement decisions, and wireless multi-hop routing with multi-receiver diversity and opportunistic routing decisions. We develop a simple max-weight algorithm that learns efficient behavior by averaging functionals of previous outcomes.",

author = "Neely, {Michael J.} and Rager, {Scott T.} and {La Porta}, {Thomas F.}",

note = "Funding Information: Manuscript received March 31, 2010; revised September 07, 2011; accepted October 02, 2011. Date of publication March 23, 2012; date of current version April 19, 2012. This work was presented in part at the Information Theory and Applications Workshop (ITA), La Jolla, CA, February2009. This work was supported in part by the DARPA IT-MANET program Grant W911NF-07-0028, the NSF Career Grant CCF-0747525, NSF Grant 0964479, the Network Science Collaborative Technology Alliance sponsored by the U.S. Army Research Laboratory W911NF-09-2-0053. Recommended by Associate Editor I. Pascha-lidis.",

year = "2012",

month = may,

doi = "10.1109/TAC.2012.2191874",

language = "English (US)",

volume = "57",

pages = "1179--1191",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

TY - JOUR

T1 - Max weight learning algorithms for scheduling in unknown environments

AU - Neely, Michael J.

AU - Rager, Scott T.

AU - La Porta, Thomas F.

N1 - Funding Information: Manuscript received March 31, 2010; revised September 07, 2011; accepted October 02, 2011. Date of publication March 23, 2012; date of current version April 19, 2012. This work was presented in part at the Information Theory and Applications Workshop (ITA), La Jolla, CA, February2009. This work was supported in part by the DARPA IT-MANET program Grant W911NF-07-0028, the NSF Career Grant CCF-0747525, NSF Grant 0964479, the Network Science Collaborative Technology Alliance sponsored by the U.S. Army Research Laboratory W911NF-09-2-0053. Recommended by Associate Editor I. Pascha-lidis.

PY - 2012/5

Y1 - 2012/5

N2 - We consider a discrete time queueing system where a controller makes a 2-stage decision every slot. The decision at the first stage reveals a hidden source of randomness with a control-dependent (but unknown) probability distribution. The decision at the second stage generates an attribute vector that depends on this revealed randomness. The goal is to stabilize all queues and optimize a utility function of time average attributes, subject to an additional set of time average constraints. This setting fits a wide class of stochastic optimization problems, including multi-user wireless scheduling with dynamic channel measurement decisions, and wireless multi-hop routing with multi-receiver diversity and opportunistic routing decisions. We develop a simple max-weight algorithm that learns efficient behavior by averaging functionals of previous outcomes.

AB - We consider a discrete time queueing system where a controller makes a 2-stage decision every slot. The decision at the first stage reveals a hidden source of randomness with a control-dependent (but unknown) probability distribution. The decision at the second stage generates an attribute vector that depends on this revealed randomness. The goal is to stabilize all queues and optimize a utility function of time average attributes, subject to an additional set of time average constraints. This setting fits a wide class of stochastic optimization problems, including multi-user wireless scheduling with dynamic channel measurement decisions, and wireless multi-hop routing with multi-receiver diversity and opportunistic routing decisions. We develop a simple max-weight algorithm that learns efficient behavior by averaging functionals of previous outcomes.

UR - http://www.scopus.com/inward/record.url?scp=84860458337&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860458337&partnerID=8YFLogxK

U2 - 10.1109/TAC.2012.2191874

DO - 10.1109/TAC.2012.2191874

M3 - Article

AN - SCOPUS:84860458337

SN - 0018-9286

VL - 57

SP - 1179

EP - 1191

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 5

M1 - 6174451

ER -

Max weight learning algorithms for scheduling in unknown environments

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this