Evolutionary policy iteration under a sampling regime for stochastic combinatorial optimization

Lauren A. Hannah; Warren Buckler Powell

doi:10.1109/TAC.2010.2042766

Evolutionary policy iteration under a sampling regime for stochastic combinatorial optimization

Lauren A. Hannah, Warren Buckler Powell

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

8 Scopus citations

Abstract

This article modifies the evolutionary policy selection algorithm of Chang et al., [1], [2], which was designed for use in infinite horizon Markov decision processes (MDPs) with a large action space to a discrete stochastic optimization problem, in an algorithm called Evolutionary Policy Iteration-Monte Carlo (EPI-MC). EPI-MC allows EPI to be used in a stochastic combinatorial optimization setting with a finite action space and a noisy cost (value) function by introducing a sampling schedule. Convergence of EPI-MC to the optimal action is proven and experimental results are given.

Original language	English (US)
Article number	5409644
Pages (from-to)	1254-1257
Number of pages	4
Journal	IEEE Transactions on Automatic Control
Volume	55
Issue number	5
DOIs	https://doi.org/10.1109/TAC.2010.2042766
State	Published - May 2010

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Keywords

Combinatorial optimization
Evolutionary policy iteration (EPI)
Monte Carlo (MC)
Stochastic optimization

Access to Document

10.1109/TAC.2010.2042766

Cite this

@article{1f88fc725677442c9fb419590bd4052b,

title = "Evolutionary policy iteration under a sampling regime for stochastic combinatorial optimization",

abstract = "This article modifies the evolutionary policy selection algorithm of Chang et al., [1], [2], which was designed for use in infinite horizon Markov decision processes (MDPs) with a large action space to a discrete stochastic optimization problem, in an algorithm called Evolutionary Policy Iteration-Monte Carlo (EPI-MC). EPI-MC allows EPI to be used in a stochastic combinatorial optimization setting with a finite action space and a noisy cost (value) function by introducing a sampling schedule. Convergence of EPI-MC to the optimal action is proven and experimental results are given.",

keywords = "Combinatorial optimization, Evolutionary policy iteration (EPI), Monte Carlo (MC), Stochastic optimization",

author = "Hannah, {Lauren A.} and Powell, {Warren Buckler}",

note = "Funding Information: Manuscript received February 11, 2009; revised August 24, 2009 and December 10, 2009. First published February 08, 2010; current version published May 12, 2010. This work was supported in part by grant AFOSR-F49620-93-1-0098 from the Air Force Office of Scientific Research. Recommended by Associate Editor C.-H. Chen.",

year = "2010",

month = may,

doi = "10.1109/TAC.2010.2042766",

language = "English (US)",

volume = "55",

pages = "1254--1257",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

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

number = "5",

}

TY - JOUR

T1 - Evolutionary policy iteration under a sampling regime for stochastic combinatorial optimization

AU - Hannah, Lauren A.

AU - Powell, Warren Buckler

N1 - Funding Information: Manuscript received February 11, 2009; revised August 24, 2009 and December 10, 2009. First published February 08, 2010; current version published May 12, 2010. This work was supported in part by grant AFOSR-F49620-93-1-0098 from the Air Force Office of Scientific Research. Recommended by Associate Editor C.-H. Chen.

PY - 2010/5

Y1 - 2010/5

N2 - This article modifies the evolutionary policy selection algorithm of Chang et al., [1], [2], which was designed for use in infinite horizon Markov decision processes (MDPs) with a large action space to a discrete stochastic optimization problem, in an algorithm called Evolutionary Policy Iteration-Monte Carlo (EPI-MC). EPI-MC allows EPI to be used in a stochastic combinatorial optimization setting with a finite action space and a noisy cost (value) function by introducing a sampling schedule. Convergence of EPI-MC to the optimal action is proven and experimental results are given.

AB - This article modifies the evolutionary policy selection algorithm of Chang et al., [1], [2], which was designed for use in infinite horizon Markov decision processes (MDPs) with a large action space to a discrete stochastic optimization problem, in an algorithm called Evolutionary Policy Iteration-Monte Carlo (EPI-MC). EPI-MC allows EPI to be used in a stochastic combinatorial optimization setting with a finite action space and a noisy cost (value) function by introducing a sampling schedule. Convergence of EPI-MC to the optimal action is proven and experimental results are given.

KW - Combinatorial optimization

KW - Evolutionary policy iteration (EPI)

KW - Monte Carlo (MC)

KW - Stochastic optimization

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

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

U2 - 10.1109/TAC.2010.2042766

DO - 10.1109/TAC.2010.2042766

M3 - Article

AN - SCOPUS:77952199276

SN - 0018-9286

VL - 55

SP - 1254

EP - 1257

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 5

M1 - 5409644

ER -

Evolutionary policy iteration under a sampling regime for stochastic combinatorial optimization

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this