A sequential supersample construction controls the generalization gap in adaptive decision-making via sequential conditional mutual information under row-wise exchangeability.
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
7 Pith papers cite this work. Polarity classification is still indexing.
7
Pith papers citing it
abstract
Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the Thirties, exploration-exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoff process associated with each option. In this survey, we focus on two extreme cases in which the analysis of regret is particularly simple and elegant: i.i.d. payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, we also analyze some of the most important variants and extensions, such as the contextual bandit model.
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
A new algorithm for online influence maximization under a total budget constraint using the independent cascade model and edge-level semi-bandit feedback, with improved regret bounds for both budgeted and cardinality settings.
No algorithm can be optimal in both stochastic and adversarial best-arm identification; a new parameter-free algorithm matches the derived lower bound up to log factors in stochastic cases while handling adversarial rewards.
A new optimistic lower-confidence-bound method for gray-box optimization that improves regret bounds for linear stochastic bandits via a recent multi-output least-squares confidence set result.
Claims minimax-optimal T^(2/3) regret for non-monotone single-index bandits, but key concentration and lower-bound steps are not established.
Introduces bounded fake data injection attacks that force a class of stochastic bandit algorithms to select a target arm in nearly all rounds at sublinear attack cost.
A survey unifying the operator-theoretic, probabilistic, and optimization-based mathematical structures underlying modern reinforcement learning algorithms.
citing papers explorer
-
Information-Theoretic Generalization Bounds for Sequential Decision Making
A sequential supersample construction controls the generalization gap in adaptive decision-making via sequential conditional mutual information under row-wise exchangeability.
-
Budgeted Online Influence Maximization
A new algorithm for online influence maximization under a total budget constraint using the independent cascade model and edge-level semi-bandit feedback, with improved regret bounds for both budgeted and cardinality settings.
-
Best of both worlds: Stochastic & adversarial best-arm identification
No algorithm can be optimal in both stochastic and adversarial best-arm identification; a new parameter-free algorithm matches the derived lower bound up to log factors in stochastic cases while handling adversarial rewards.
-
Gray-Box Optimization using Optimism in the Face of Uncertainty
A new optimistic lower-confidence-bound method for gray-box optimization that improves regret bounds for linear stochastic bandits via a recent multi-output least-squares confidence set result.
-
Optimal Regret for Single Index Bandits
Claims minimax-optimal T^(2/3) regret for non-monotone single-index bandits, but key concentration and lower-bound steps are not established.
-
Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection
Introduces bounded fake data injection attacks that force a class of stochastic bandit algorithms to select a target arm in nearly all rounds at sublinear attack cost.
-
Mathematical methods of reinforcement learning
A survey unifying the operator-theoretic, probabilistic, and optimization-based mathematical structures underlying modern reinforcement learning algorithms.