On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access

Keqin Liu; Qing Zhao

doi:10.1109/CDC.2009.5400366

On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access

Keqin Liu^*, Qing Zhao

^*Corresponding author for this work

Department of Financial and Actuarial Mathematics

Cornell University

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

3 Citations (Scopus)

Abstract

We consider a class of restless multi-armed bandit problems that arises in multi-channel opportunistic communications, where channels are modeled as independent and stochastically identical Gilbert-Elliot channels and channel state observations are subject to errors. We show that the myopic channel selection policy has a semi-universal structure that obviates the need to know the Markovian transition probabilities of the channel states. Based on this structure, we establish closed-form lower and upper bounds on the steady-state throughput achieved by the myopic policy. Furthermore, we characterize the approximation factor of the myopic policy to bound its worst-case performance loss with respect to the optimal performance.

Original language	English
Title of host publication	Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3592-3597
Number of pages	6
ISBN (Print)	9781424438716
DOIs	https://doi.org/10.1109/CDC.2009.5400366
Publication status	Published - 2009
Event	48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 - Shanghai, China Duration: 15 Dec 2009 → 18 Dec 2009

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009
Country/Territory	China
City	Shanghai
Period	15/12/09 → 18/12/09

Keywords

Dynamic multi-channel access
Myopic policy
Restless multi-armed bandit

Access to Document

10.1109/CDC.2009.5400366

Cite this

Liu, K., & Zhao, Q. (2009). On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access. In Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 (pp. 3592-3597). Article 5400366 (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2009.5400366

Liu, Keqin ; Zhao, Qing. / On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access. Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. Institute of Electrical and Electronics Engineers Inc., 2009. pp. 3592-3597 (Proceedings of the IEEE Conference on Decision and Control).

@inproceedings{ab37f2a2d39b491e9686db24940bc64a,

title = "On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access",

abstract = "We consider a class of restless multi-armed bandit problems that arises in multi-channel opportunistic communications, where channels are modeled as independent and stochastically identical Gilbert-Elliot channels and channel state observations are subject to errors. We show that the myopic channel selection policy has a semi-universal structure that obviates the need to know the Markovian transition probabilities of the channel states. Based on this structure, we establish closed-form lower and upper bounds on the steady-state throughput achieved by the myopic policy. Furthermore, we characterize the approximation factor of the myopic policy to bound its worst-case performance loss with respect to the optimal performance.",

keywords = "Dynamic multi-channel access, Myopic policy, Restless multi-armed bandit",

author = "Keqin Liu and Qing Zhao",

year = "2009",

doi = "10.1109/CDC.2009.5400366",

language = "English",

isbn = "9781424438716",

series = "Proceedings of the IEEE Conference on Decision and Control",

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

pages = "3592--3597",

booktitle = "Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009",

note = "48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 ; Conference date: 15-12-2009 Through 18-12-2009",

}

Liu, K & Zhao, Q 2009, On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access. in Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009., 5400366, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 3592-3597, 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009, Shanghai, China, 15/12/09. https://doi.org/10.1109/CDC.2009.5400366

On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access. / Liu, Keqin; Zhao, Qing.
Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. Institute of Electrical and Electronics Engineers Inc., 2009. p. 3592-3597 5400366 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access

AU - Liu, Keqin

AU - Zhao, Qing

PY - 2009

Y1 - 2009

N2 - We consider a class of restless multi-armed bandit problems that arises in multi-channel opportunistic communications, where channels are modeled as independent and stochastically identical Gilbert-Elliot channels and channel state observations are subject to errors. We show that the myopic channel selection policy has a semi-universal structure that obviates the need to know the Markovian transition probabilities of the channel states. Based on this structure, we establish closed-form lower and upper bounds on the steady-state throughput achieved by the myopic policy. Furthermore, we characterize the approximation factor of the myopic policy to bound its worst-case performance loss with respect to the optimal performance.

AB - We consider a class of restless multi-armed bandit problems that arises in multi-channel opportunistic communications, where channels are modeled as independent and stochastically identical Gilbert-Elliot channels and channel state observations are subject to errors. We show that the myopic channel selection policy has a semi-universal structure that obviates the need to know the Markovian transition probabilities of the channel states. Based on this structure, we establish closed-form lower and upper bounds on the steady-state throughput achieved by the myopic policy. Furthermore, we characterize the approximation factor of the myopic policy to bound its worst-case performance loss with respect to the optimal performance.

KW - Dynamic multi-channel access

KW - Myopic policy

KW - Restless multi-armed bandit

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

U2 - 10.1109/CDC.2009.5400366

DO - 10.1109/CDC.2009.5400366

M3 - Conference Proceeding

AN - SCOPUS:77950804455

SN - 9781424438716

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 3592

EP - 3597

BT - Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

Y2 - 15 December 2009 through 18 December 2009

ER -

Liu K, Zhao Q. On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access. In Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. Institute of Electrical and Electronics Engineers Inc. 2009. p. 3592-3597. 5400366. (Proceedings of the IEEE Conference on Decision and Control). doi: 10.1109/CDC.2009.5400366

On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel access

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this