Approximation algorithms for correlated knapsacks and non-martingale bandits

Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In the stochastic knapsack problem, we are given a knapsack of size B, and a set of items whose sizes and rewards are drawn from a known probability distribution. To know the actual size and reward we have to schedule the item - when it completes, we get to know these values. The goal is to schedule the items (possibly making adaptive decisions based on the sizes seen so far) to maximize the expected total reward of items which successfully pack into the knapsack. We know constant-factor approximations when (i) the rewards and sizes are independent, and (ii) we cannot prematurely cancel items after we schedule them. What if either or both assumptions are relaxed? Related stochastic packing problems are the multi-armed bandit (and budgeted learning) problems, here one is given several arms which evolve in a specified stochastic fashion with each pull, and the goal is to (adaptively) decide which arms to pull, in order to maximize the expected reward obtained after B pulls in total. Much recent work on this problem focuses on the case when the evolution of each arm follows a martingale, i.e., when the expected reward from one pull of an arm is the same as the reward at the current state. What if the rewards do not form a martingale? In this paper, we give O(1)-approximation algorithms for the stochastic knapsack problem with correlations and/or cancellations. Extending the ideas developed here, we give O(1)-approximations for MAB problems without the martingale assumption. Indeed, we can show that previously proposed linear programming relaxations for these problems have large integrality gaps. So we propose new time-indexed LP relaxations, using a decomposition and "gap-filling" approach, we convert these fractional solutions to distributions over strategies, and then use the LP values and the time ordering information from these strategies to devise randomized adaptive scheduling algorithms.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Number of pages10
StatePublished - 2011
Event2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States
Duration: Oct 22 2011Oct 25 2011

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428


Other2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Country/TerritoryUnited States
CityPalm Springs, CA


  • Approximation Algorithms
  • Multi-Armed Bandits
  • Stochastic Optimization

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Approximation algorithms for correlated knapsacks and non-martingale bandits'. Together they form a unique fingerprint.

Cite this