Linearly parameterized bandits

DOI10.1287/MOOR.1100.0446MaRDI QIDQ3169099zbMATH OpenOpenAlexFDO

Authors Paat Rusmevichientong, John N. Tsitsiklis

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.3465

zbMATH Keywords

adaptive controlmulti-armed banditparametric model

Mathematics Subject Classification ID

Robustness and adaptive procedures (parametric inference) (62F35) Sequential estimation (62L12) Adaptive control/observation systems (93C40) Application models in control theory (93C95) Stochastic learning and adaptive control (93E35)

Abstract: We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an $r$-dimensional random vector $mathbfZinmathbb{R}^r$, where $rgeq2$. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order $Theta(rsqrtT)$, by establishing a lower bound for an arbitrary policy, and showing that a matching upper bound is obtained through a policy that alternates between exploration and exploitation phases. The phase-based policy is also shown to be effective if the set of arms satisfies a strong convexity condition. For the case of a general set of arms, we describe a near-optimal policy whose regret and Bayes risk admit upper bounds of the form $O(rsqrtTlo{g}^{3/2}T)$.

Recommendations

• A linear response bandit problem
• Finite-time analysis of the multiarmed bandit problem
• X-armed bandits
• Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
• Nonparametric bandit methods

Cited in

(43)

• A penalized bandit algorithm
• Linear Thompson sampling revisited
• Reinforcement learning with immediate rewards and linear hypotheses
• Best arm identification in generalized linear bandits
• Regret lower bound and optimal algorithm for high-dimensional contextual linear bandit
• Stochastic continuum-armed bandits with additive models: minimax regrets and adaptive algorithm
• Secure cumulative reward maximization in linear stochastic bandits
• Online collaborative filtering on graphs
• Optimal learning in linear regression with combinatorial feature selection
• On Solving Finite State Multi-Armed Bandit Problem by Linear Programming
• Active learning of Bayesian linear models with high-dimensional binary features by parameter confidence-region estimation
• Profile-based bandit with unknown profiles
• Reward maximization under uncertainty: leveraging side-observations on networks
• Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
• Learning to optimize via information-directed sampling
• Technical note -- A note on the equivalence of upper confidence bounds and Gittins indices for patient agents
• A bandit-learning approach to multifidelity approximation
• scientific article; zbMATH DE number 7626799 (Why is no real title available?)
• scientific article; zbMATH DE number 7625185 (Why is no real title available?)
• Ranking and Selection with Covariates for Personalized Decision Making
• Dynamic learning and decision making via basis weight vectors
• Online resource allocation with personalized learning
• MNL-bandit: a dynamic learning approach to assortment selection
• Online decision making with high-dimensional covariates
• Online Network Revenue Management Using Thompson Sampling
• Learning in combinatorial optimization: what and how to explore
• Dynamic assortment optimization with changing contextual information
• A linear response bandit problem
• Dynamic pricing with multiple products and partially specified demand distribution
• Mean square convergence rates for maximum quasi-likelihood estimators
• Learning to optimize via posterior sampling
• Satisficing in Time-Sensitive Bandit Learning
• Randomized allocation with arm elimination in a bandit problem with covariates
• Technical note—Knowledge gradient for selection with covariates: Consistency and computation
• A tractable online learning algorithm for the multinomial logit contextual bandit
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
• Empirical Gittins index strategies with -explorations for multi-armed bandit problems
• Multi-armed linear bandits with latent biases
• An optimal selection for ensembles of influential projects
• Contextual bandits with stage-wise constraints
• Optimal sequential stochastic shortest path interdiction
• A technical note on non-stationary parametric bandits: existing mistakes and preliminary solutions
• Statistical inference for online decision making with Lasso loss function: in a contextual multi-armed bandit setting

This page was built for publication: Linearly parameterized bandits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169099)