A PAC algorithm in relative precision for bandit problem with costly sampling

Marie Billaud Friess (), Arthur Macherey (), Anthony Nouy () and Clémentine Prieur ()
Additional contact information
Marie Billaud Friess: Nantes Université Centrale Nantes, LMJL, UMR CNRS 6629
Arthur Macherey: Nantes Université Centrale Nantes, LMJL, UMR CNRS 6629
Anthony Nouy: Nantes Université Centrale Nantes, LMJL, UMR CNRS 6629
Clémentine Prieur: Université Grenoble Alpes

Mathematical Methods of Operations Research, 2022, vol. 96, issue 2, No 1, 185 pages

Abstract: Abstract This paper considers the problem of maximizing an expectation function over a finite set, or finite-arm bandit problem. We first propose a naive stochastic bandit algorithm for obtaining a probably approximately correct (PAC) solution to this discrete optimization problem in relative precision, that is a solution which solves the optimization problem up to a relative error smaller than a prescribed tolerance, with high probability. We also propose an adaptive stochastic bandit algorithm which provides a PAC-solution with the same guarantees. The adaptive algorithm outperforms the mean complexity of the naive algorithm in terms of number of generated samples and is particularly well suited for applications with high sampling cost.

Keywords: Bandit algorithm; Probably approximately correct algorithm; Relative precision; Concentration inequalities; Monte-Carlo estimates (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-022-00769-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:96:y:2022:i:2:d:10.1007_s00186-022-00769-x

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-022-00769-x

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().