Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
From MaRDI portal
Abstract: We present and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions, and observes some subset of the associated losses. This naturally models several situations where the losses of different actions are related, and knowing the loss of one action provides information on the loss of other actions. Moreover, it generalizes and interpolates between the well studied full-information setting (where all losses are revealed) and the bandit setting (where only the loss of the action chosen by the player is revealed). We provide several algorithms addressing different variants of our setting, and provide tight regret bounds depending on combinatorial properties of the information feedback structure.
Recommendations
- The Nonstochastic Multiarmed Bandit Problem
- Improved algorithms for bandit with graph feedback via regret decomposition
- A Structured Multiarmed Bandit Problem and the Greedy Policy
- The multi-armed bandit problem: an efficient nonparametric solution
- Stochastic convex optimization with bandit feedback
- Bayesian nonparametric bandits
- Multi-Armed Bandits: Theory and Applications to Online Learning in Networks
- Optimal exploration-exploitation in a multi-armed bandit problem with non-stationary rewards
- Nonstationary bandits with habituation and recovery dynamics
- Randomized allocation with nonparametric estimation for contextual multi-armed bandits with delayed rewards
Cites work
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 986986 (Why is no real title available?)
- scientific article; zbMATH DE number 7306905 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A decision-theoretic generalization of on-line learning and an application to boosting
- Arbitrary side observations in bandit problems
- Bandit problems with side observations
- Combinatorial bandits
- Efficient algorithms for online decision problems
- How to use expert advice
- Learning Theory
- Linearly parameterized bandits
- On tail probabilities for martingales
- On the independence number of random graphs
- Partial monitoring -- classification, regret bounds, and algorithms
- Prediction, Learning, and Games
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Regret bounds and minimax policies under partial monitoring
- The Nonstochastic Multiarmed Bandit Problem
- The multi-armed bandit problem with covariates
- The probabilistic method
- The weighted majority algorithm
Cited in
(15)- scientific article; zbMATH DE number 7306905 (Why is no real title available?)
- Improved algorithms for bandit with graph feedback via regret decomposition
- Reward maximization under uncertainty: leveraging side-observations on networks
- Small-Loss Bounds for Online Learning with Partial Information
- Improved high-probability regret for adversarial bandits with time-varying feedback graphs
- Online learning with off-policy feedback
- Feedback graph regret bounds for Thompson sampling and UCB
- Interactive learning of a dynamic structure
- An efficient algorithm for cooperative semi-bandits
- Best arm identification for contaminated bandits
- Nonstochastic bandits: Countable decision set, unbounded costs and reactive environments
- Semi-parametric contextual bandits with graph-Laplacian regularization
- Improved regret bounds for bandits with expert advice
- An \(\alpha \)-regret analysis of adversarial bilateral trade
- Delay and cooperation in nonstochastic bandits
This page was built for publication: Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596721)
