Fetching the paper…
Reading the bibliography…
In this paper, we consider several finite-horizon Bayesian multi-armed bandit problems with side constraints which are computationally intractable (NP-Hard) and for which no optimal (or near optimal) algorithms are known to exist with sub-exponential running time.
Sequential Analysis
A. Wald · 1947
Earlier work this paper cites.
Bayes and minmax solutions of sequential decision problems
K. J. Arrow, D. Blackwell, and M. A. Girshick · 1949
Earlier work this paper cites.
Some aspects of the sequential design of experiments
H. Robbins · 1952
Earlier work this paper cites.
On sequential designs for maximizing the sum of n n observations
R. N. Bradt, S. M. Johnson, and S. Karlin · 1956
Earlier work this paper cites.
Sequential analysis with delayed observations
T. W. Anderson · 1964
Earlier work this paper cites.
On sequential decision problems with delayed observations
Y. Suzuki · 1966
Earlier work this paper cites.
Sequential decision for a binomial parameter with delayed observations
S. C. Choi and V. A. Clark · 1970
Earlier work this paper cites.
On a scheduling problem in sequential analysis
S. Ehrenfeld · 1970
Earlier work this paper cites.
A dynamic allocation index for the sequential design of experiments
J. C. Gittins and D. M. Jones · 1972
Earlier work this paper cites.
A dynamic allocation index for the sequential design of experiments
J. C. Gittins and D. M. Jones · 1972
Earlier work this paper cites.
A two-armed bandit theory of market pricing
M. Rothschild · 1974
Earlier work this paper cites.
Adaptive treatment assignment methods and clinical trials
R. Simon · 1977
Earlier work this paper cites.
Job-search and the theory of turnover
B. Jovanovich · 1979
Earlier work this paper cites.
The search for optimality in clinical trials
P. Armitage · 1985
Earlier work this paper cites.
Asymptotically efficient adaptive allocation rules
T. L. Lai and H. Robbins · 1985
Earlier work this paper cites.
Job-search and labor market analysis
D. Mortensen · 1985
Earlier work this paper cites.
The two-armed bandit with delayed responses
S. G. Eick · 1988
Earlier work this paper cites.
Restless bandits: Activity allocation in a changing world
P. Whittle · 1988
Earlier work this paper cites.
Elements of Information Theory
T. M. Cover and J. A. Thomas · 1991
Earlier work this paper cites.
Denumerable-armed bandits
J. S. Banks and R. K. Sundaram · 1992
Earlier work this paper cites.
Switching costs and the gittins index
J. S. Banks and R. K. Sundaram · 1994
Earlier work this paper cites.
A short proof of the Gittins index theorem
J. N. Tsitsiklis · 1994
Earlier work this paper cites.
Conservation laws, extended polymatroids and multi-armed bandit problems: A unified polyhedral approach
D. Bertsimas and J. Nino-Mora · 1996
Cited alongside, same era.
How to use expert advice
N. Cesa-Bianchi, Y. Freund, D. Haussler, D. P. Helmbold, R. E. Schapire, and M. K. Warmuth · 1997
Cited alongside, same era.
Optimization flow control, i: Basic algorithm and convergence
S. Low and D. E. Lapsley · 1999
Cited alongside, same era.
Restless bandits, linear programming relaxations, and a primal-dual index heuristic
D. Bertsimas and J. Niño-Mora · 2000
Cited alongside, same era.
Dynamic Programming and Optimal Control
D. Bertsekas · 2001
Cited alongside, same era.
Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation
K. Jain and V. V. Vazirani · 2001
Approximation algorithms for budgeted learning problems
S. Guha and K. Munagala · 2007
Later among the works it cites.
Relaxations of weakly coupled stochastic dynamic programs
D. Adelman and A. J. Mersereau · 2008
Later among the works it cites.
Improved algorithms for orienteering and related problems
C. Chekuri, N. Korula, and M. Pál · 2008
Later among the works it cites.
Approximating the stochastic knapsack problem: The benefit of adaptivity
B. C. Dean, M. X. Goemans, and J. Vondrak · 2008
Later among the works it cites.
Sequential design of experiments via linear programming
S. Guha and K. Munagala · 2008
Later among the works it cites.
Multi-UAV dynamic routing with partial observations using restless bandits allocation indices
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Restless bandits, partial conservation laws and indexability
J. Niño-Mora · 2001
Cited alongside, same era.
Finite-time analysis of the multiarmed bandit problem
P. Auer, N. Cesa-Bianchi, and P. Fischer · 2002
Cited alongside, same era.
Optimal learning and experimentation in bandit problems
M. Brezzi and T.-L. Lai · 2002
Cited alongside, same era.
Active learning in discrete input spaces
J. Schneider and A. Moore · 2002
Cited alongside, same era.
A measurement-based analysis of multihoming
A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman · 2003
Cited alongside, same era.
The nonstochastic multiarmed bandit problem
P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire · 2003
Cited alongside, same era.
J. L. Ny, M. Dahleh, and E. Feron · 2008
Later among the works it cites.
An online algorithm for maximizing submodular functions
M. J. Streeter and D. Golovin · 2008
Later among the works it cites.
Explore/exploit schemes for web content optimization
D. Agarwal, B.-C. Chen, and P. Elango · 2009
Later among the works it cites.
Automated experiment-driven management of (database) systems
S. Babu, N. Borisov, S. Duan, H. Herodotou, and V. Thummala · 2009
Later among the works it cites.
Reflective control for an elastic cloud appliation: An automated experiment workbench
A. Demberel, J. Chase, and S. Babu · 2009
Later among the works it cites.
The ratio index for budgeted learning, with applications
A. Goel, S. Khanna, and B. Null · 2009
Later among the works it cites.
Multi-armed bandits with metric switching costs
S. Guha and K. Munagala · 2009
Later among the works it cites.
Maximizing sequence-submodular functions and its application to online advertising
S. Alaei and A. Malekian · 2010
Later among the works it cites.
How to probe for an extreme value
A. Goel, S. Guha, and K. Munagala · 2010
Later among the works it cites.
Iterated allocations with delayed feedback
S. Guha, K. Munagala, and M. Pál · 2010
Later among the works it cites.
Approximation algorithms for restless bandit problems
S. Guha, K. Munagala, and P. Shi · 2010
Later among the works it cites.
The irrevocable multiarmed bandit problem
V. F. Farias and R. Madan · 2011
Later among the works it cites.
Multi-Armed Bandit Allocation Indices
J. Gittins, K. Glazebrook, and R. Weber · 2011
Later among the works it cites.
Adaptive submodular optimization under matroid constraints
D. Golovin and A. Krause · 2011
Later among the works it cites.
Approximation algorithms for correlated knapsacks and non-martingale bandits
A. Gupta, R. Krishnaswamy, M. Molinaro, and R. Ravi · 2011
Later among the works it cites.
Profiling, what-if analysis, and cost-based optimization of mapreduce programs
H. Herodotou and S. Babu · 2011
Later among the works it cites.
Approximate indexability and bandit problems with concave rewards and delayed feedback
S. Guha and K. Munagala · 2013
Closest in time.