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 action poisoning attacks improve LinUCB's performance by changing action signals.
problem Improving understanding of adversarial attacks on contextual bandit algorithms.
method Proposed action poisoning attacks in white-box and black-box settings.
result Action poisoning attacks can force LinUCB to pull a target arm frequently with low cost.
New algorithms reduce regret in adversarial linear contextual bandits.
problem Adversarial linear contextual bandits with changing loss functions.
method Developed two algorithms: RealLinExp3 and RobustLinExp3.
result Achieved optimal regret bounds for the first time.
Malicious agents can manipulate linear contextual bandits to pull desired arms with logarithmic overhead.
problem Malicious attacks on linear contextual bandit algorithms in various domains.
method Study and propose an efficient algorithm to perform adversarial attacks on linear contextual bandits.
result Malicious agents can force a linear contextual bandit algorithm to pull any desired arm T − o ( T ) T - o(T) T − o ( T ) times over a horizon of T T T steps with logarithmic modifications. Improved regret bounds for adversarial linear contextual bandits.
problem Adversarial linear contextual bandits with changing loss functions.
method Truncated continuous exponential weights algorithm over the probability simplex, analyzing with linear bandit setting without contexts.
result Second-order bound of i l d e O ( K d V T ) ilde O(K\sqrt{d V_T}) i l d e O ( K d V T ) and first-order bound of i l d e O ( K d L T ∗ ) ilde O(K\sqrt{d L_T^*}) i l d e O ( K d L T ∗ ) . 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 ) . Improved online Lasso reduces regret in sparse linear contextual bandits.
problem Sparse linear contextual bandit problem with inefficient sampling.
method Perturbed adversary approach to alleviate sampling inefficiency.
result Online Lasso achieves O ( k T log d ) \mathcal{O}(\sqrt{kT\log d}) O ( k T log d ) regret bound. 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.
New algorithm reduces linear contextual bandit regret with adversarial corruption.
problem Linear contextual bandit with adversarial reward corruption.
method Optimism in the face of uncertainty principle, weighted ridge regression.
result Achieves nearly optimal regret for both corrupted and uncorrupted cases.
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 algorithm resists corruption in linear contextual bandits.
problem Adversarial corruption in linear contextual bandits.
method Variance-aware algorithm with multi-level partition and adaptive confidence sets.
result Regret bound of i l d e O ( C 2 d ∑ t = 1 T σ t 2 + C 2 R d T ) ilde{O}(C^2d\sqrt{\sum_{t = 1}^T σ_t^2} + C^2R\sqrt{dT}) i l d e O ( C 2 d ∑ t = 1 T σ t 2 + C 2 R d T ) . 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.
A new algorithm tackles adversarial linear contextual bandits using kernelized loss functions.
problem Online learning in adversarial linear contextual bandits with flexible loss functions.
method Proposes a computationally efficient algorithm using an optimistically biased estimator for reproducing kernel Hilbert space loss functions.
result Achieves near-optimal regret guarantees under polynomial and exponential eigendecay assumptions.
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.
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.
New findings on universal learning in contextual bandits with adversarial rewards.
problem Learning in contextual bandits with time-varying, adversarial rewards.
method Characterization of learnable processes and necessary/sufficient conditions for universal learning.
result Optimistic universal learning for contextual bandits with adversarial rewards is impossible in general.
A federated learning algorithm tackles linear bandits with adversarial actions, achieving optimal regret bounds.
problem Federated linear bandits with finite adversarial action sets.
method FedSupLinUCB algorithm, extending SupLinUCB and OFUL principles.
result Achieves a total regret of i l d e O ( d T ) ilde{O}(\sqrt{d T}) i l d e O ( d T ) , matching minimax lower bound and being order-optimal. New algorithm reduces regret in RL with adversarial corruption.
problem Adversarial corruption in reinforcement learning.
method Uncertainty-weighted least-squares regression and weighted uncertainty estimator.
result Achieves regret of i l d e O ( T + ζ ) ilde{O}(\sqrt{T} + ζ) i l d e O ( T + ζ ) for contextual bandits. New algorithms robust to adversarial data achieve optimal performance.
problem Adversarial robustness in high-dimensional online learning problems.
method Alternating minimization scheme combining least-squares and convex reweighting.
result Achieves optimal robustness guarantees without distributional assumptions.
The paper tackles minimax optimality in continuum contextual bandits with Hölder continuity.
problem Minimizing regret in a continuum of contexts with Hölder continuity.
method Proves a static-to-contextual regret conversion theorem and analyzes various dependency cases.
result Achieves minimax optimal contextual regret for convex and strongly convex bandits.
Improved regret bounds for structured linear contextual bandits with Gaussian noise.
problem Optimizing bandit learning algorithms for structured contexts with Gaussian perturbations.
method Proposed simple greedy algorithms for structured linear contextual bandits with Gaussian noise.
result Unified regret analysis for structured parameters with geometric quantities as bounds.
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. 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 algorithm reduces contextual bandits to efficient regression.
problem Developing efficient algorithms for contextual bandits with general function classes.
method Reduction from contextual bandits to online regression with oracle.
result First universal and optimal reduction with no overhead.
New algorithm tackles dynamic query routing to multiple embedding models.
problem Dynamic query routing to multiple embedding models under adversarial conditions.
method Formalized as adversarial contextual linear bandit with low-rank experts, proposed HPG algorithm.
result HPG algorithm achieves linearized policy regret of i l d e O ( s M T ) ilde{\mathcal O}(s\sqrt{M T}) i l d e O ( s M T ) . New algorithms balance collaboration and adversarial behavior in linear bandits.
problem Minimizing regret in a collaborative linear bandit problem with adversarial agents.
method Robust collaborative phased elimination algorithm with tight analyses.
result Achieves near-optimal regret bounds of $O\left(α+ 1/\sqrt{M}
ight) \sqrt{dT}$ for good agents.
New algorithms combat adversarial attacks in stochastic linear bandits.
problem Adversarial attacks on stochastic linear bandit rewards.
method Two variants of Robust Phased Elimination algorithms, one knowing C C C and one not. result Near-optimal regret in non-corrupted case and additive terms dependent on C C C . 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. Improved algorithm for contextual bandits with reduced regret.
problem Adversarial contextual bandits with i.i.d. contexts.
method Oracle-efficient relaxation with O ( T 2 3 ( K log ( ∣ Π ∣ ) ) 1 3 ) O(T^{\frac{2}{3}}(K\log(|Π|))^{\frac{1}{3}}) O ( T 3 2 ( K log ( ∣Π∣ ) ) 3 1 ) regret bound. result First to improve regret bound and match original bound for stochastic case.
Improved ε ε ε -greedy handles strategic bidding in PPC auctions.
problem Strategic bidding in PPC auctions with personalization and corruptions.
method Extended ε ε ε -greedy to handle strategic arms in contextual multi-arm bandit. result ε ε ε -greedy is robust to adversarial corruptions and degrades linearly with corruption. 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 adversarial attack method using structured search and contextual bandits.
problem Black-box adversarial attacks on deep learning models.
method Structured search space and Bayesian optimization for contextual bandits.
result Achieves state-of-the-art success rates and query efficiencies.
The paper tackles robust policy learning in multitask contextual bandits with adversarial users.
problem Learning optimal policies in multitask contextual bandits with a small fraction of adversarial users.
method Developed efficient robust mean estimators for both uni-variate and high-dimensional random variables.
result Lower bound of i l d e Ω ( min ( S , A ) ⋅ α 2 / ε 2 ) ildeΩ(\min(S,A) \cdot α^2 / ε^2) i l d e Ω ( min ( S , A ) ⋅ α 2 / ε 2 ) per-user interactions to learn an ε ε ε -optimal policy for good users. 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…
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.
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. New algorithm reduces regret in contextual bandits with many near-boundary contexts.
problem High regret in contextual bandits with many near-boundary contexts.
method Hierarchical nearest neighbour approach, holding out contexts for computation.
result Eradicates high regret in adversarial contextual bandits.
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.
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.
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.
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…
Adaptive algorithms minimize regret in matching markets with contextual arm preferences.
problem Minimizing regret in matching markets with context-dependent player utilities.
method Developed adaptive algorithms for stochastic and adversarial contexts, providing upper and lower bounds.
result Achieved sublinear regret bounds for both stochastic and adversarial contexts.
Improved regret bounds for contextual bandits considering variance sequences.
problem Establishing lower bounds for contextual bandits with variance-dependent regret.
method Developed variance-dependent lower bounds for linear contextual bandits under two settings: fixed and adaptive variance sequences.
result Lower bounds match upper bounds of SAVE algorithm up to logarithmic factors.
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).
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 ) . Study online learning with off-policy feedback in adversarial bandit problems.
problem Learning with limited direct feedback in sequential decision making.
method Proposed algorithms that adapt pessimistic reward estimators to handle unknown behavior policy.
result Guaranteed regret bounds scaling with policy mismatch, improving performance against well-covered comparators.
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.
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.