Surveillance in an abruptly changing world via multiarmed bandits

Vaibhav Srivastava; Paul Reverdy; Naomi E. Leonard

doi:10.1109/CDC.2014.7039462

Surveillance in an abruptly changing world via multiarmed bandits

Vaibhav Srivastava, Paul Reverdy, Naomi E. Leonard

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

29 Scopus citations

Abstract

We study a path planning problem in an environment that is abruptly changing due to the arrival of unknown spatial events. The objective of the path planning problem is to collect the data that is most evidential about the events. We formulate this problem as a multiarmed bandit (MAB) problem with Gaussian rewards and change points, and address the fundamental tradeoff between learning the true event (exploration), and collecting the data that is most evidential about the true event (exploitation). We extend the switching-window UCB algorithm for MAB problems with bounded rewards and change points to the context of correlated Gaussian rewards and develop the switching-window UCL (SW-UCL) algorithm. We extend the SW-UCL algorithm to an adaptive SW-UCL algorithm that utilizes statistical change detection to adapt the SW-UCL algorithm. We also develop a block SW-UCL algorithm that reduces the number of transitions among arms in the SW-UCL algorithm, and is more amenable to robotic applications.

Original language	English (US)
Title of host publication	53rd IEEE Conference on Decision and Control,CDC 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	692-697
Number of pages	6
Edition	February
ISBN (Electronic)	9781479977468
DOIs	https://doi.org/10.1109/CDC.2014.7039462
State	Published - 2014
Externally published	Yes
Event	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States Duration: Dec 15 2014 → Dec 17 2014

Publication series

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

Conference

Conference	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Country/Territory	United States
City	Los Angeles
Period	12/15/14 → 12/17/14

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Access to Document

10.1109/CDC.2014.7039462

Cite this

Srivastava, V., Reverdy, P., & Leonard, N. E. (2014). Surveillance in an abruptly changing world via multiarmed bandits. In 53rd IEEE Conference on Decision and Control,CDC 2014 (February ed., pp. 692-697). Article 7039462 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2015-February, No. February). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2014.7039462

Surveillance in an abruptly changing world via multiarmed bandits. / Srivastava, Vaibhav; Reverdy, Paul; Leonard, Naomi E.
53rd IEEE Conference on Decision and Control,CDC 2014. February. ed. Institute of Electrical and Electronics Engineers Inc., 2014. p. 692-697 7039462 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2015-February, No. February).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Srivastava, V, Reverdy, P & Leonard, NE 2014, Surveillance in an abruptly changing world via multiarmed bandits. in 53rd IEEE Conference on Decision and Control,CDC 2014. February edn, 7039462, Proceedings of the IEEE Conference on Decision and Control, no. February, vol. 2015-February, Institute of Electrical and Electronics Engineers Inc., pp. 692-697, 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014, Los Angeles, United States, 12/15/14. https://doi.org/10.1109/CDC.2014.7039462

@inproceedings{69f86817846243ca95ad45eabafffb96,

title = "Surveillance in an abruptly changing world via multiarmed bandits",

abstract = "We study a path planning problem in an environment that is abruptly changing due to the arrival of unknown spatial events. The objective of the path planning problem is to collect the data that is most evidential about the events. We formulate this problem as a multiarmed bandit (MAB) problem with Gaussian rewards and change points, and address the fundamental tradeoff between learning the true event (exploration), and collecting the data that is most evidential about the true event (exploitation). We extend the switching-window UCB algorithm for MAB problems with bounded rewards and change points to the context of correlated Gaussian rewards and develop the switching-window UCL (SW-UCL) algorithm. We extend the SW-UCL algorithm to an adaptive SW-UCL algorithm that utilizes statistical change detection to adapt the SW-UCL algorithm. We also develop a block SW-UCL algorithm that reduces the number of transitions among arms in the SW-UCL algorithm, and is more amenable to robotic applications.",

author = "Vaibhav Srivastava and Paul Reverdy and Leonard, {Naomi E.}",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 ; Conference date: 15-12-2014 Through 17-12-2014",

year = "2014",

doi = "10.1109/CDC.2014.7039462",

language = "English (US)",

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

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

number = "February",

pages = "692--697",

booktitle = "53rd IEEE Conference on Decision and Control,CDC 2014",

edition = "February",

}

TY - GEN

T1 - Surveillance in an abruptly changing world via multiarmed bandits

AU - Srivastava, Vaibhav

AU - Reverdy, Paul

AU - Leonard, Naomi E.

PY - 2014

Y1 - 2014

N2 - We study a path planning problem in an environment that is abruptly changing due to the arrival of unknown spatial events. The objective of the path planning problem is to collect the data that is most evidential about the events. We formulate this problem as a multiarmed bandit (MAB) problem with Gaussian rewards and change points, and address the fundamental tradeoff between learning the true event (exploration), and collecting the data that is most evidential about the true event (exploitation). We extend the switching-window UCB algorithm for MAB problems with bounded rewards and change points to the context of correlated Gaussian rewards and develop the switching-window UCL (SW-UCL) algorithm. We extend the SW-UCL algorithm to an adaptive SW-UCL algorithm that utilizes statistical change detection to adapt the SW-UCL algorithm. We also develop a block SW-UCL algorithm that reduces the number of transitions among arms in the SW-UCL algorithm, and is more amenable to robotic applications.

AB - We study a path planning problem in an environment that is abruptly changing due to the arrival of unknown spatial events. The objective of the path planning problem is to collect the data that is most evidential about the events. We formulate this problem as a multiarmed bandit (MAB) problem with Gaussian rewards and change points, and address the fundamental tradeoff between learning the true event (exploration), and collecting the data that is most evidential about the true event (exploitation). We extend the switching-window UCB algorithm for MAB problems with bounded rewards and change points to the context of correlated Gaussian rewards and develop the switching-window UCL (SW-UCL) algorithm. We extend the SW-UCL algorithm to an adaptive SW-UCL algorithm that utilizes statistical change detection to adapt the SW-UCL algorithm. We also develop a block SW-UCL algorithm that reduces the number of transitions among arms in the SW-UCL algorithm, and is more amenable to robotic applications.

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

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

U2 - 10.1109/CDC.2014.7039462

DO - 10.1109/CDC.2014.7039462

M3 - Conference contribution

AN - SCOPUS:84988286023

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 692

EP - 697

BT - 53rd IEEE Conference on Decision and Control,CDC 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014

Y2 - 15 December 2014 through 17 December 2014

ER -

Surveillance in an abruptly changing world via multiarmed bandits

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this