Optimal exploration-exploitation in a multi-armed bandit problem with non-stationary rewards
From MaRDI portal
(Redirected from Publication:5113912)
Abstract: In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Reward realizations are only observed when an arm is selected, and the gambler's objective is to maximize his cumulative expected earnings over some given horizon of play T. To do this, the gambler needs to acquire information about arms (exploration) while simultaneously optimizing immediate rewards (exploitation); the price paid due to this trade off is often referred to as the regret, and the main question is how small can this price be as a function of the horizon length T. This problem has been studied extensively when the reward distributions do not change over time; an assumption that supports a sharp characterization of the regret, yet is often violated in practical settings. In this paper, we focus on a MAB formulation which allows for a broad range of temporal uncertainties in the rewards, while still maintaining mathematical tractability. We fully characterize the (regret) complexity of this class of MAB problems by establishing a direct link between the extent of allowable reward "variation" and the minimal achievable regret. Our analysis draws some connections between two rather disparate strands of literature: the adversarial and the stochastic MAB frameworks.
Recommendations
Cites work
- A decision-theoretic generalization of on-line learning and an application to boosting
- An analog of the minimax theorem for vector payoffs
- Arm-acquiring bandits
- Asymptotically efficient adaptive allocation rules
- Contextual bandits with similarity information
- Dynamic assortment with demand learning for seasonal consumer goods
- Finite-time analysis of the multiarmed bandit problem
- scientific article; zbMATH DE number 3128728 (Why is no real title available?)
- scientific article; zbMATH DE number 4078557 (Why is no real title available?)
- scientific article; zbMATH DE number 4087408 (Why is no real title available?)
- scientific article; zbMATH DE number 3474804 (Why is no real title available?)
- scientific article; zbMATH DE number 3638998 (Why is no real title available?)
- scientific article; zbMATH DE number 194374 (Why is no real title available?)
- scientific article; zbMATH DE number 6253908 (Why is no real title available?)
- Learning and Strategic Pricing
- Non-stationary stochastic optimization
- On upper-confidence bound policies for switching bandit problems
- Prediction, Learning, and Games
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Regret bounds for restless Markov bandits
- Regret in the on-line decision problem
- Restless Bandits, Linear Programming Relaxations, and a Primal-Dual Index Heuristic
- Some aspects of the sequential design of experiments
- The Nonstochastic Multiarmed Bandit Problem
Cited in
(22)- Bayesian adversarial multi-node bandit for optimal smart grid protection against cyber attacks
- Multi-armed bandit with sub-exponential rewards
- Fully probabilistic design of strategies with estimator
- Lipschitzness is all you need to tame off-policy generative adversarial imitation learning
- Reinforcement learning and evolutionary algorithms for non-stationary multi-armed bandit problems
- Non-stationary stochastic optimization
- time-decaying bandits for non-stationary problems
- scientific article; zbMATH DE number 1985272 (Why is no real title available?)
- Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
- The Nonstochastic Multiarmed Bandit Problem
- Regulating greed over time in multi-armed bandits
- Setting Reserve Prices in Second-Price Auctions with Unobserved Bids
- Nonstationary bandits with habituation and recovery dynamics
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Robust sequential design for piecewise-stationary multi-armed bandit problem in the presence of outliers
- Optimal activation of halting multi‐armed bandit models
- Multi-armed bandit problem with online clustering as side information
- Model-based preference quantification
- A dynamic programming strategy to balance exploration and exploitation in the bandit problem
- Continual learning as computationally constrained reinforcement learning
- Adaptive smooth nonstationary bandits
- Nonstochastic bandits: Countable decision set, unbounded costs and reactive environments
This page was built for publication: Optimal exploration-exploitation in a multi-armed bandit problem with non-stationary rewards
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113912)
