Finite-time analysis for the knowledge-gradient policy

DOI10.1137/16M1073388MaRDI QIDQ4610155zbMATH OpenOpenAlexWikidataFDO

Authors Yingfei Wang, Warren Powell

Publication date 5 April 2018

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.04624

zbMATH Keywords

stochastic controlranking and selectionsequential decision analysis

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Statistical ranking and selection procedures (62F07) Sequential statistical analysis (62L10) Bayesian problems; characterization of Bayes procedures (62C10)

Abstract: We consider sequential decision problems in which we adaptively choose one of finitely many alternatives and observe a stochastic reward. We offer a new perspective of interpreting Bayesian ranking and selection problems as adaptive stochastic multi-set maximization problems and derive the first finite-time bound of the knowledge-gradient policy for adaptive submodular objective functions. In addition, we introduce the concept of prior-optimality and provide another insight into the performance of the knowledge gradient policy based on the submodular assumption on the value of information. We demonstrate submodularity for the two-alternative case and provide other conditions for more general problems, bringing out the issue and importance of submodularity in learning problems. Empirical experiments are conducted to further illustrate the finite time behavior of the knowledge gradient policy.

Recommendations

• A Knowledge-Gradient Policy for Sequential Information Collection
• The knowledge-gradient policy for correlated normal beliefs
• Refined knowledge-gradient policy for learning probabilities
• The knowledge gradient algorithm for a general class of online learning problems
• Hierarchical knowledge gradient for sequential sampling

Cites work

• scientific article; zbMATH DE number 43985 (Why is no real title available?)
• scientific article; zbMATH DE number 3638998 (Why is no real title available?)
• scientific article; zbMATH DE number 1494998 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A Bayesian Approach to Some Best Population Problems
• A Knowledge-Gradient Policy for Sequential Information Collection
• An analysis of approximations for maximizing submodular set functions—I
• Asymptotically efficient adaptive allocation rules
• Bandits With Heavy Tail
• Bayesian data analysis.
• Bayesian look ahead one-stage sampling allocations for selection of the best population
• Efficient Dynamic Simulation Allocation in Ordinal Optimization
• Efficient global optimization of expensive black-box functions
• Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
• Finite-time analysis of the multiarmed bandit problem
• Global optimization of stochastic black-box systems via sequential kriging meta-models
• Hierarchical knowledge gradient for sequential sampling
• Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• On upper-confidence bound policies for switching bandit problems
• Optimal learning for sequential sampling with non-parametric beliefs
• Regret bounds for sleeping experts and bandits
• Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
• Selecting a selection procedure
• Simulation budget allocation for further enhancing the efficiency of ordinal optimization
• The Data-Correcting Algorithm for the Minimization of Supermodular Functions
• The knowledge-gradient algorithm for sequencing experiments in drug discovery
• The knowledge-gradient policy for correlated normal beliefs

Cited in

(8)

• Finding the optimal exploration-exploitation trade-off online through Bayesian risk estimation and minimization
• The knowledge gradient algorithm for a general class of online learning problems
• Information collection on a graph
• A Knowledge-Gradient Policy for Sequential Information Collection
• Refined knowledge-gradient policy for learning probabilities
• Technical note—Knowledge gradient for selection with covariates: Consistency and computation
• ON THE IDENTIFICATION AND MITIGATION OF WEAKNESSES IN THE KNOWLEDGE GRADIENT POLICY FOR MULTI-ARMED BANDITS
• Hierarchical knowledge gradient for sequential sampling

Describes a project that uses

Uses Software

• BayesDA
• EGO

This page was built for publication: Finite-time analysis for the knowledge-gradient policy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4610155)