Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . New algorithm reduces regret from sqrt(T) to polylog(T) in stochastic contextual linear bandits.
problem Achieving logarithmic regret in stochastic contextual linear bandits.
method Low Regret Stochastic Contextual Bandits ( exttt{LR-SCB}) algorithm, exploiting stochastic contexts and parameter estimation.
result Logarithmic regret (polylog(T)) achieved, improving over sqrt(T) lower bound.
First robust bandit algorithm for contextual bandits with sub-linear regret.
problem Vulnerability of linear contextual bandit algorithms to adversarial attacks.
method Proposes a robust bandit algorithm for stochastic linear contextual bandits under fully adaptive and omniscient attacks.
result Sub-linear regret under various attacks without requiring attack information.
New algorithm improves learning efficiency in multi-task contextual bandits.
problem Improving learning efficiency in multi-task contextual bandits.
method Alternating projected gradient descent (GD) and minimization estimator for low-rank feature matrix recovery.
result Proved regret bound for multi-task learning algorithm.
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden simple multi-armed bandit structure in which the rewards are independent of the contextual information. Algorithms that are designed solely for one of the regimes are known to be sub-optimal for the alternate regime…
New algorithm reduces regret with diverse contexts in bandits.
problem Impact of context diversity on stochastic linear contextual bandits.
method Design of LinUCB-d algorithm and analysis of its regret performance.
result Cumulative expected regret is bounded by a constant under diverse context assumption.
New algorithm for contextual bandits with linear constraints using regression.
problem Contextual bandits with packing and covering constraints.
method Modular Lagrangian approach via regression.
result First vanishing-regret guarantees for CBwLC (or CBwK).
New algorithms protect user data while optimizing personalized decisions.
problem Personalized decision-making with private user data.
method Developed LDP algorithms for stochastic generalized linear bandits using SGD and OLS.
result Achieved the same regret bound as non-privacy settings with LDP.
Study on selecting between base algorithms in stochastic bandit problems.
problem Model selection in stochastic environments with contextual information.
method Developed a meta-algorithm-base algorithm abstraction with a smoothing transformation for optimal O ( T ) O(\sqrt{T}) O ( T ) guarantees. result Optimal O ( T ) O(\sqrt{T}) O ( T ) model selection guarantees for stochastic contextual bandit problems. Designs a single policy for collecting data to train near-optimal policies.
problem Engineering overhead in deploying minimax procedures for stochastic linear contextual bandits.
method Designs a single stochastic policy to collect data from which a near-optimal policy can be extracted.
result The designed policy can collect data from which a near-optimal policy can be extracted.
A collaborative algorithm reduces regret in federated linear contextual bandits.
problem Optimizing decision-making in federated learning with heterogeneous data.
method Fed-PE algorithm, leveraging geometric structure of rewards, multi-client G-optimal design.
result Achieves near-optimal regrets with logarithmic communication costs.
Study on adaptivity constraints in linear contextual bandits with optimal design.
problem Impact of adaptivity constraints on linear contextual bandits.
method Two models of limited adaptivity: batch learning and rare policy switches. Proposed distributional optimal design.
result Achieves minimax-optimal regret with optimal number of policy switches and batches.
Develops a Best-of-Both-Worlds algorithm for linear contextual bandits with Tsallis entropy.
problem Linear contextual bandits with i.i.d. contexts.
method Follow-The-Regularized-Leader (FTRL) with Tsallis entropy.
result Achieves $O\left(\log(T)^{\frac{1+β}{2+β}}T^{\frac{1}{2+β}}
ight)$ regret under margin condition.
Improved Thompson Sampling for high-dimensional sparse bandits.
problem Stochastic linear contextual bandits with high-dimensional features.
method Thompson Sampling with spike-and-slab priors and variational inference.
result Nearly optimal upper bound on expected cumulative regret.
A new method for sparse linear bandits reduces exploration-exploitation tradeoff.
problem Sparse linear bandits in high-dimensional settings with finite actions.
method Best subset selection for parameter estimation and doubly growing epochs for regret minimization.
result Achieves nearly dimension-independent regret of i l d e O ( s T ) ilde{\mathcal{O}}(s\sqrt{T}) i l d e O ( s T ) with high probability. New algorithm reduces contextual bandit identification to argmax calls.
problem Best-arm identification in stochastic contextual bandits.
method Instance-optimal PAC algorithm using argmax oracle calls.
result First instance-dependent PAC sample complexity for contextual bandits.
Develops a strategy to minimize loss in both stochastic and adversarial environments for linear contextual bandits.
problem Linear contextual bandits with adversarial corruption.
method Proposes a novel strategy called Best-of-Both-Worlds (BoBW) RealFTRL, extending RealLinExp3 and FTRL.
result Regret upper bound of $O\left(\min\left\{\frac{(\log(T))^3}{Δ_{*}} + \sqrt{\frac{C(\log(T))^3}{Δ_{*}}},\ \ \sqrt{T}(\log(T))^2
ight\}
ight)$ , showing effectiveness in both stochastic and adversarial environments.
Algorithm minimizes regret in dueling bandits with contextualized utilities.
problem Minimizing regret in dueling bandits with context-dependent utilities.
method Proposes CoLSTIM algorithm based on perturbed utility estimates.
result Achieves regret of order i l d e O ( d T ) ilde O(\sqrt{dT}) i l d e O ( d T ) . A new algorithm combines SGD and Thompson Sampling for contextual bandits.
problem Finding efficient algorithms for contextual bandits with low time and memory complexity.
method Online Stochastic Gradient Descent (SGD) combined with Thompson Sampling.
result Achieves i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret with linear time complexity in T T T and d d d . A new algorithm selects models for contextual bandits, reducing regret.
problem Model selection for stochastic contextual bandits under realizability assumption.
method Adaptive Contextual Bandit (ACB) algorithm, successive refinement phases.
result ACB algorithm achieves similar regret bound to known algorithms, with a model selection cost.
Proposes a new algorithm for non-stationary bandits.
problem Non-stationary reward distributions in contextual bandits.
method Multiscale changepoint detection for adaptive learning.
result Regret bound analysis and superior performance in experiments.
Adapts two algorithms for online learning with delayed rewards.
problem Online learning with delayed rewards in generalized linear contextual bandits.
method Modifies upper confidence bounds and Thompson sampling algorithms for delayed rewards.
result Both algorithms can be made robust to delays, improving their performance.
New method for online statistical inference in contextual bandits using SGD.
problem Online decision-making in contextual bandits with statistical inference.
method Weighted stochastic gradient descent for adaptive data collection.
result Asymptotic normality of the parameter estimator with improved efficiency.
New algorithms for private generalized linear contextual bandits.
problem Private estimation and optimization for generalized linear models under differential privacy.
method Developed algorithms for stochastic and adversarial contexts under shuffle and joint differential privacy.
result Achieved private regret bounds for generalized linear models, differing from non-private rates by factors of d / ε \sqrt{d/\varepsilon} d / ε and d / ε \sqrt{d/\varepsilon} d / ε respectively. New algorithms minimize regret in both adversarial and stochastic contexts.
problem Minimizing regret in linear contextual bandits.
method Best-of-both-worlds algorithms using FTRL with Shannon entropy regularizer.
result Achieves near-optimal regret bounds in both adversarial and stochastic regimes.
We study the contextual linear bandit problem, a version of the standard stochastic multi-armed bandit (MAB) problem where a learner sequentially selects actions to maximize a reward which depends also on a user provided per-round context. Though the context is chosen arbitrarily or adversarially, the reward is assumed…
An algorithm for maximizing rewards under linear cost constraints.
problem Maximizing rewards while adhering to cost constraints in a linear bandit problem.
method Proposes an upper-confidence bound algorithm called optimistic pessimistic linear bandit (OPLB) for constrained contextual linear bandits.
result Proves an O ~ ( d T τ − c 0 ) \widetilde{\mathcal{O}}(\frac{d\sqrt{T}}{τ-c_0}) O ( τ − c 0 d T ) bound on regret for the proposed algorithm. New algorithm for fair ranking in contextual bandits with concave rewards.
problem Fair ranking in recommendation systems.
method Geometric interpretation of CBCR as optimization, Frank-Wolfe analyses.
result First algorithm with provably vanishing regret for CBCR.
Two algorithms address limited adaptivity in generalized linear contextual bandits.
problem Limited adaptivity in generalized linear contextual bandits.
method Two algorithms, B-GLinCB and RS-GLinCB, designed for two settings of limited adaptivity.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret in both settings. New method tackles high-dimensional contextual bandits with flexible kernel models.
problem Maximizing rewards in decision-making scenarios with many features.
method Introduces stochastic assumptions and no-regret learning for Gaussian kernels.
result Achieves no-regret learning even with feature dimensions growing with samples.
GLCB uses Gated Linear Networks for online contextual bandits.
problem Online learning in contextual bandits with uncertainty estimation.
method Gated Linear Networks (GLNs) for prediction and uncertainty estimation.
result GLCB outperforms state-of-the-art methods in online contextual bandits.
Optimal algorithm for maximizing rewards in contextual bandits with resource constraints.
problem Maximizing rewards in contextual bandits with resource constraints.
method Proposed a universal and optimal algorithmic framework for CBwK by reducing it to online regression.
result Established the optimality of the proposed algorithm for various function classes.
This paper achieves optimal regret bounds for locally private linear contextual bandit.
problem Designing locally private linear contextual bandit algorithms with optimal regret bounds.
method New algorithmic and analytical ideas, including mean absolute deviation analysis and layered principal component regression.
result Achieves an i l d e O ( T ) ilde O(\sqrt{T}) i l d e O ( T ) regret upper bound for locally private linear contextual bandit. Data that is gathered adaptively --- via bandit algorithms, for example --- exhibits bias. This is true both when gathering simple numeric valued data --- the empirical means kept track of by stochastic bandit algorithms are biased downwards --- and when gathering more complicated data --- running hypothesis tests on c…
Paper studies CLO with partial feedback, improving decision-making in uncertain contexts.
problem Improving decision-making in contexts with uncertain cost coefficients using partial feedback.
method Unified class of offline learning algorithms for CLO with different types of feedback, using IERM framework.
result Fast-rate regret bound for IERM with partial feedback and misspecified model classes.
This paper studies semiparametric contextual bandits, a generalization of the linear stochastic bandit problem where the reward for an action is modeled as a linear function of known action features confounded by an non-linear action-independent term. We design new algorithms that achieve O ~ ( d T ) \tilde{O}(d\sqrt{T}) O ~ ( d T ) regret …
Paper improves SLCB regret bound for bounded noise.
problem Stochastic linear contextual bandits with bounded noise.
method Set-membership estimation (SME) and optimism in the face of uncertainty (OFU).
result Improved regret bound of O ( log T ) O(\log T) O ( log T ) . Paper tackles domain adaptation for contextual bandits with sub-linear regret.
problem Adapting contextual bandit algorithms across domains with distribution shift.
method Learn a bandit model for the target domain using feedback from the source domain.
result Sub-linear regret bound maintained across domains.
A framework for auto-tuning hyper-parameters in contextual bandit algorithms.
problem Auto-tuning hyper-parameters in real-time for contextual bandit algorithms.
method Proposes a Syndicated Bandits framework to learn multiple hyper-parameters dynamically.
result Achieves optimal regret bounds under certain scenarios and handles multiple contextual bandit algorithms.
NeuralRBMLE tackles explore-exploit trade-offs in contextual bandits with neural networks.
problem Stochastic contextual bandit problem with general bounded reward functions.
method Reward-biased maximum likelihood estimation with neural networks to enforce exploration.
result Both NeuralRBMLE variants achieve O ~ ( T ) \widetilde{\mathcal{O}}(\sqrt{T}) O ( T ) regret. Bayesian bandit algorithms with approximate inference improve regret bounds in stochastic linear bandits.
problem Theoretical justification for Bayesian bandit algorithms with approximate inference in stochastic linear bandits.
method Proposed a theoretical framework to analyze approximate inference impact and conducted frequentist regret analysis on LinTS and LinBUCB.
result LinTS and LinBUCB preserve their original regret upper bounds with larger constant terms in approximate inference settings.
A simple algorithm reduces federated contextual linear bandits' regret efficiently.
problem Solving federated contextual linear bandits with asynchronous agents.
method Proposed a simple algorithm exttt{FedLinUCB} based on optimism principle.
result Proved exttt{FedLinUCB} has bounded regret i l d e O ( d ∑ m = 1 M T m ) ilde{O}(d\sqrt{\sum_{m=1}^M T_m}) i l d e O ( d ∑ m = 1 M T m ) and communication complexity i l d e O ( d M 2 ) ilde{O}(dM^2) i l d e O ( d M 2 ) . IDS improves reinforcement learning with contextual information.
problem Optimizing IDS for contextual reinforcement learning.
method Investigated contextual bandit problems and proposed a computationally-efficient IDS.
result Contextual IDS outperforms conditional IDS by considering future contexts.
This paper improves offline contextual bandits using distributional robustness.
problem Improving offline contextual bandits with robustness.
method Extends Distributionally Robust Optimization (DRO) for offline contextual bandits, introducing a convex reformulation of Counterfactual Risk Minimization.
result Automatic calibration of asymptotic confidence intervals for policy optimization.
New method achieves near-optimal regret without simulator.
problem Adversarial linear contextual bandits with unknown loss vectors.
method Near-optimally reduces regret to sqrt(T) without simulator.
result Achieves regret of sqrt(T) without simulator, improving existing methods.
New algorithms for model selection in linear contextual bandits without feature diversity conditions.
problem Model selection in linear contextual bandits without feature diversity conditions.
method Data-adaptive algorithms that provide model selection guarantees without feature diversity conditions.
result O(d^α T^{1-α}) model selection guarantees with no feature diversity conditions.
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state-of-the-art methods. However, many ques…
A new framework tunes hyperparameters in real-time for contextual bandits.
problem Optimizing hyperparameters for contextual bandits in real-time.
method CDT (Continuous Dynamic Tuning) framework using Zooming TS algorithm.
result Achieves sublinear regret and performs better than existing methods.