Explore first, exploit next: the true shape of regret in bandit problems
From MaRDI portal
Publication:5219722
Abstract: We revisit lower bounds on the regret in the case of multi-armed bandit problems. We obtain non-asymptotic, distribution-dependent bounds and provide straightforward proofs based only on well-known properties of Kullback-Leibler divergences. These bounds show in particular that in an initial phase the regret grows almost linearly, and that the well-known logarithmic growth of the regret only holds in a final phase. The proof techniques come to the essence of the information-theoretic arguments used and they are deprived of all unnecessary complications.
Recommendations
- Finite-time analysis of the multiarmed bandit problem
- Pure exploration in multi-armed bandits problems
- Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
- Pure exploration in finitely-armed and continuous-armed bandits
- Exploration-exploitation policies with almost sure, arbitrarily slow growing asymptotic regret
Cites work
- Asymptotically efficient adaptive allocation rules
- Finite-time analysis of the multiarmed bandit problem
- Finite-time lower bounds for the two-armed bandit problem
- scientific article; zbMATH DE number 1220667 (Why is no real title available?)
- scientific article; zbMATH DE number 3322635 (Why is no real title available?)
- Kullback-Leibler upper confidence bounds for optimal sequential allocation
- Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards
- On the complexity of best-arm identification in multi-armed bandit models
- Online learning and game theory. A quick overview with recent results and applications
- Optimal adaptive policies for sequential allocation problems
- Prediction, Learning, and Games
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- The Nonstochastic Multiarmed Bandit Problem
- The sample complexity of exploration in the multi-armed bandit problem
- UCB revisited: improved regret bounds for the stochastic multi-armed bandit problem
Cited in
(15)- Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives
- Fano's inequality for random variables
- Asymptotically optimal algorithms for budgeted multiple play bandits
- Pure exploration in finitely-armed and continuous-armed bandits
- 10.1162/153244303321897663
- Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models
- On multi-armed bandit designs for dose-finding trials
- Exploration-exploitation policies with almost sure, arbitrarily slow growing asymptotic regret
- Pair-matching: link prediction with adaptive queries
- Anytime-valid t -tests and confidence sequences for Gaussian means with unknown variance
- CRIMED: lower and upper bounds on regret for bandits with unbounded stochastic corruption
- On best-arm identification with a fixed budget in non-parametric multi-armed bandits
- Episodic reinforcement learning in finite MDPs: minimax lower bounds revisited
- Efficient algorithms for stochastic repeated second-price auctions
- Statistical complexity and optimal algorithms for nonlinear ridge bandits
This page was built for publication: Explore first, exploit next: the true shape of regret in bandit problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219722)
