Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback

DOI10.1162/neco_a_01299zbMath1454.91060arXiv1902.10582OpenAlexW2947781524WikidataQ97597326 ScholiaQ97597326MaRDI QIDQ3386400

Masashi Sugiyama, Atsushi Miyauchi, Yuko Kuroki, Liyuan Xu, Junya Honda

Publication date: 4 January 2021

Published in: Neural Computation (Search for Journal in Brave)

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

zbMATH Keywords

polynomial-time approximation algorithmdecision-making modelsemi-bandit settingstochastic multiple-arm identification

Mathematics Subject Classification ID

Decision theory (91B06) Approximation algorithms (68W25) Combinatorial probability (60C99) Mathematical economics and fuzziness (91B86)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial bandits
• Asymptotically efficient adaptive allocation rules
• Random sampling and greedy sparsification for matroid optimization problems
• Approximation of the quadratic knapsack problem
• Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs
• Efficient crowdsourcing of unknown experts using bounded multi-armed bandits
• Detecting high log-densities
• Submodularity and Randomized rounding techniques for Optimal Experimental Design
• The Equivalence of Two Extremum Problems
• Powers of tensors and fast matrix multiplication
• Multi-armed bandit problems with multiple plays and switching cost
• Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: I.I.D. rewards
• Greedily Finding a Dense Subgraph
• Optimal Design of Experiments
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Prediction, Learning, and Games
• The dense \(k\)-subgraph problem