Imperial College London
Portrait Picture

DrCiaraPike-Burke

Faculty of Natural Sciences, Department of Mathematics

Lecturer in Statistics
 
 
 
//

Contact

 

+44 (0)20 7594 2976c.pike-burke

 
 
//

Location

 

522Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inproceedings{Pike-Burke:2017,
author = {Pike-Burke, C and Grunewalder, S},
pages = {1114--1122},
publisher = {MICROTOME PUBLISHING},
title = {Optimistic planning for the stochastic knapsack problem},
url = {http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000509368500119&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202},
year = {2017}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - The stochastic knapsack problem is a stochastic resource allocation problem that arises frequently and yet is exceptionally hard to solve. We derive and study an optimistic planning algorithm specifically designed for the stochastic knapsack problem. Unlike other optimistic planning algorithms for MDPs, our algorithm, OpStoK, avoids the use of discounting and is adaptive to the amount of resources available. We achieve this behavior by means of a concentration inequality that simultaneously applies to capacity and reward estimates. Crucially, we are able to guarantee that the aforementioned confidence regions hold collectively over all time steps by an application of Doob’s inequality. We demonstrate that the method returns an ε-optimal solution to the stochastic knapsack problem with high probability. To the best of our knowledge, our algorithm is the first which provides such guarantees for the stochastic knapsack problem. Furthermore, our algorithm is an anytime algorithm and will return a good solution even if stopped prematurely. This is particularly important given the difficulty of the problem. We also provide theoretical conditions to guarantee OpStoK does not expand all policies and demonstrate favorable performance in a simple experimental setting.
AU  - Pike-Burke,C
AU  - Grunewalder,S
EP  - 1122
PB  - MICROTOME PUBLISHING
PY  - 2017///
SN  - 2640-3498
SP  - 1114
TI  - Optimistic planning for the stochastic knapsack problem
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000509368500119&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - http://proceedings.mlr.press/v54/pike-burke17a.html
UR  - http://hdl.handle.net/10044/1/83608
ER  -
Download