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 ) . Optimal algorithm for identifying best arm in stochastic linear bandits with fixed confidence.
problem Identifying the best arm in stochastic linear bandits with fixed confidence.
method Extending an algorithm designed for Best Arm Identification to the ε ε ε -Thresholding Bandit Problem (TBP). result Asymptotically optimal algorithm for TBP.
A meta-UCB method combines stochastic bandit algorithms.
problem Combining multiple stochastic bandit algorithms efficiently.
method Meta-UCB procedure solving an N-armed bandit problem.
result Final regret depends only on the best base algorithm's regret.
Paper studies attacks on bandit algorithms and shows how attackers can manipulate data to hijack behavior.
problem Potential attacks on bandit algorithms can cause catastrophic loss in real-world applications.
method Proposes a framework of offline and online attacks on bandit algorithms using convex optimization and adaptive strategies.
result Attackers can force bandit algorithms to pull target arms with high probability by manipulating data.
Improved algorithms for stochastic linear bandits using tighter confidence sequences.
problem Stochastic linear bandits with improved worst-case regret guarantees.
method Novel tail bound for adaptive martingale mixtures to construct tighter confidence sequences.
result Linear bandit algorithm achieves competitive worst-case regret.
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.
RONM method reduces regret in stochastic convex bandits with decreasing noise.
problem Stochastic convex bandit problem with decreasing noise.
method Regularized Online Newton Method (RONM) based on Online Newton Method (ONM).
result RONM achieves polylogarithmic regret in time horizon n.
New algorithm reduces regret in stochastic bandit convex optimization.
problem Optimizing decisions in uncertain environments with convex losses.
method Introduces a second-order method for zeroth-order stochastic convex bandits.
result Regret bound of ( 1 + r / d ) [ d 1.5 n + d 3 ] p o l y l o g ( n , d , r ) (1 + r/d)[d^{1.5} \sqrt{n} + d^3] polylog(n, d, r) ( 1 + r / d ) [ d 1.5 n + d 3 ] p o l y l o g ( n , d , r ) . Improved regret bounds for Tsallis-INF in adversarial bandits and corruptions.
problem Adversarial bandits and corruptions in multiarmed bandit problems.
method Improved regret bounds for Tsallis-INF algorithm.
result Achieves $\mathcal{O}\left(\left(\sum_{i
eq i^*} \frac{1}{Δ_i}
ight)\log_+\left(\frac{(K-1)T}{\left(\sum_{i
eq i^*} \frac{1}{Δ_i}
ight)^2}
ight)+\sqrt{C\left(\sum_{i
eq i^*}\frac{1}{Δ_i}
ight)\log_+\left(\frac{(K-1)T}{C\sum_{i
eq i^*}\frac{1}{Δ_i}}
ight)}
ight)$ regret bound.
A new algorithm reduces regret in cooperative multi-agent bandits with heavy-tailed data.
problem Cooperative multi-agent bandits with heavy-tailed data.
method MP-UCB algorithm incorporating robust estimation with message-passing protocol.
result Optimal regret bounds for MP-UCB in various settings.
Optimal semi-bandit algorithm for both stochastic and adversarial environments.
problem Optimal semi-bandit algorithm for both stochastic and adversarial environments.
method Developed a general semi-bandit algorithm that achieves O ( log T ) \mathcal{O}(\log T) O ( log T ) regret for stochastic and O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) regret for adversarial environments without regime or T T T knowledge. result First algorithm to achieve optimal O ( log T ) \mathcal{O}(\log T) O ( log T ) and O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) regret simultaneously for stochastic and adversarial environments. Combines multiple bandit algorithms to create a nearly optimal single algorithm.
problem Designing a single bandit algorithm that performs nearly as well as the best individual algorithm in a stochastic environment.
method Develops two general corralling algorithms that achieve favorable regret guarantees.
result The regret of the corralling algorithms is no worse than the best individual algorithm's performance.
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.
New algorithm reduces regret in corrupted bandits.
problem Stochastic multi-armed bandits with adversarial corruption.
method A new algorithm that is agnostic to corruption levels.
result Regret is nearly optimal and can handle significant corruption.
New model for display advertising with stochastic and adversarial components.
problem Display advertising with stochastic and adversarial click-through-rates.
method Adversarial scaling model; two algorithms tested: action elimination and mirror descent.
result Two algorithms are robust to adversarial scaling.
Adversaries can manipulate bandit algorithms to control chosen actions.
problem Manipulating stochastic bandit algorithms to influence chosen actions.
method Proposes an attack against ε ε ε -greedy and UCB algorithms without knowing mean rewards. result Attackers can control actions with logarithmic effort, making it easy to hijack behavior.
Paper tackles stochastic k k k -submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k k k -submodular functions with full-bandit feedback. method Proposes online algorithms for various k k k -submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α α α -regret bounds for multiple k k k -submodular stochastic combinatorial multi-armed bandit problems. New algorithm minimizes regret in stochastic bandits.
problem Minimizing regret in stochastic bandit models.
method Proposes kl-UCB ++ algorithm for exponential families.
result Proves asymptotic and minimax optimality.
Study on policy gradient for stochastic bandits using diffusion approximation.
problem Improving policy gradient methods for stochastic bandits with optimal regret bounds.
method Continuous-time diffusion approximation of policy gradient with learning rate analysis.
result Proved optimal regret bound of O ( k log ( k ) log ( n ) / η ) O(k \log(k) \log(n) / η) O ( k log ( k ) log ( n ) / η ) for η = O ( Δ 2 / log ( n ) ) η= O(Δ^2/\log(n)) η = O ( Δ 2 / log ( n )) . A new algorithm improves stochastic linear bandit performance using residual bootstrap.
problem Improving performance in stochastic linear bandit problems.
method Residual bootstrap exploration to estimate mean reward and pull the arm with the highest estimate.
result Proposed algorithm exttt{LinReBoot} achieves high-probability sub-linear regret under mild conditions.
Differential privacy reduces bias in adaptive data gathering.
problem Bias in adaptive data gathering, including numeric and complex data.
method Apply differential privacy to reduce bias and correct p-values.
result Near optimal regret bounds for differentially private bandit algorithms.
Study on Pareto optimality in multi-objective bandit problems.
problem Pareto optimality in multi-objective multi-armed bandit problems.
method Formulated adversarial multi-objective multi-armed bandit, defined Pareto regrets, presented algorithms, established upper and lower bounds.
result New algorithms are optimal in adversarial settings and nearly optimal in stochastic settings.
Improved EXP3++ algorithm reduces regret in stochastic bandits.
problem Stochastic and adversarial multiarmed bandits.
method New gap estimation strategy combined with EXP3++.
result Regret reduced from ( ln t ) 3 (\ln t)^3 ( ln t ) 3 to ( ln t ) 2 (\ln t)^2 ( ln t ) 2 in stochastic regime. Paper proposes efficient algorithms for bandit problems with costly sampling.
problem Maximizing expectation function over a finite set with high sampling cost.
method Proposes naive and adaptive stochastic bandit algorithms for PAC solution.
result Adaptive algorithm outperforms naive in terms of number of samples.
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. 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 tackles stochastic bandits with unknown scale using kurtosis bounds.
problem Existing strategies for stochastic bandits require known scale parameters.
method Develops a scale-free algorithm for stochastic bandits with a bound on kurtosis.
result Generalizes results for Gaussian and uniform distributions to non-parametric setup.
Study shows efficient neural network approach for stochastic bandits.
problem Optimizing decisions in uncertain environments with neural network models.
method OFU-ReLU algorithm that balances exploration and exploitation, using a transformed feature space.
result Achieves i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret guarantee for stochastic bandits with ReLU neural networks. Safe linear stochastic bandits ensure safe exploration with optimal regret.
problem Ensuring safe exploration in stochastic bandits while minimizing regret.
method Combining known safe arms with exploratory arms to safely expand the set of safe arms over time.
result The algorithm achieves an expected regret of O ( T log ( T ) ) O(\sqrt{T}\log (T)) O ( T log ( T )) . KL-UCB+ policy outperforms KL-UCB empirically in stochastic bandits.
problem Optimizing decisions in a stochastic bandit problem.
method Demonstrates a simple proof of asymptotic optimality for KL-UCB+ policy.
result KL-UCB+ policy achieves asymptotically optimal regret bound.
New algorithm tackles delayed feedback in Lipschitz bandits with sublinear regret.
problem Delayed feedback in Lipschitz bandits.
method Design of algorithms for bounded and unbounded stochastic delays.
result Sublinear regret guarantees for both bounded and unbounded delays.
Meta-learning improves performance in stochastic linear bandits.
problem Selecting a learning algorithm that performs well across multiple bandit tasks.
method Regularized OFUL algorithm with a bias vector, estimating bias within the learning-to-learn setting.
result Meta-learning strategies improve performance when the number of tasks grows and task variance is small.
Study optimizes dueling bandit learning with a stochastic mirror descent algorithm.
problem Optimizing dueling bandit learning with noisy comparison feedback.
method Proposes a stochastic mirror descent algorithm for continuous dueling bandit.
result Achieves an O ( T log T ) O(\sqrt{T\log T}) O ( T log T ) -regret bound under strong convexity and smoothness assumptions. 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.
New algorithms tackle RKHS bandits with reduced complexity and improved performance.
problem Adversarial and stochastic RKHS bandit problems with high computational complexity.
method Combining approximation theory with misspecified linear bandit methods.
result First general algorithm for adversarial RKHS bandit problem.
A new bandit model with stochastic context distributions and UCB algorithm.
problem Learning optimal actions in a stochastic environment with hidden contexts.
method Stochastic contextual bandit model and UCB algorithm.
result Order-optimal high-probability bound on cumulative regret for linear and kernelized reward functions.
Improved UCB method for stochastic bandits using distance tuning.
problem Improving performance in stochastic bandit problems.
method Tuning confidence bounds based on bandit distance.
result Empirically shows increased performance compared to existing methods.
Paper addresses privacy and robustness in stochastic linear bandits.
problem Stochastic linear bandits with differential privacy and adversarial robustness.
method Logarithmic batch queries, arm elimination algorithm, two privacy models.
result First algorithms providing differential privacy and adversarial robustness.
Balances and eliminates base algorithms in bandits and RL to bound total regret.
problem Model selection in bandits and reinforcement learning with unknown optimal regret.
method Balances and eliminates base algorithms based on candidate regret bounds.
result Total regret bound is the best valid candidate regret bound times a small multiplicative factor.
New algorithm tackles stochastic bandits with varying arm-dependent delays.
problem Applying existing algorithms to stochastic delayed bandit settings is restricted by strong assumptions on delay distributions.
method Proposes a simple UCB-based algorithm called PatientBandits that weakens assumptions on delay distributions.
result Provides bounds on regret and performance lower bounds for the PatientBandits algorithm.
Unified analysis of perturbation-based strategies in stochastic and adversarial bandit problems.
problem Optimality of perturbation-based strategies in multi-armed bandit problems.
method Unified regret analysis for stochastic and adversarial settings, using perturbations of sub-Weibull and bounded support.
result Unified bounds for perturbations in both stochastic and adversarial settings, with optimal perturbations of Frechet-type.
New algorithm reduces exploration in structured stochastic bandits.
problem Wide class of stochastic bandit problems with known structural properties.
method Developed OSSB algorithm that matches minimal exploration rates of sub-optimal arms.
result OSSB's regret matches asymptotic instance-specific regret lower bound.
Factored bandits model learns with limited feedback using decomposable actions.
problem Limited feedback learning with decomposable actions.
method Introduces factored bandits model, provides anytime algorithm, and matching upper and lower bounds.
result Improves regret bounds for utility-based dueling bandits.
New UCB algorithms tackle contextual bandits with stochastic experts, achieving instance-dependent regret bounds.
problem Contextual bandits with stochastic experts, a variation of traditional stochastic contextual bandits.
method Proposes UCB algorithms using importance sampling to estimate mean rewards from multiple experts.
result Achieves instance-dependent regret bounds of $\mathcal{O}\left(λ(\pmbμ)\mathcal{M}\log T/Δ
ight)$ , with λ ( μ ) λ(\pmbμ) λ ( μ ) typically O ( log N ) \mathcal{O}(\log N) O ( log N ) . New UCB algorithms resist contamination in bandit problems.
problem Stochastic bandit problems with ε-contaminated rewards.
method Robust mean estimators and crUCB algorithms.
result Achieves O(√KTlogT) regret for small contamination proportions.
Unified framework for high-dimensional bandit problems with low-dimensional structures.
problem Stochastic high-dimensional bandit problems with low-dimensional structures.
method Proposed a simple unified algorithm and a general analysis framework for the regret upper bound.
result Unified algorithm achieves comparable regret bounds in various high-dimensional bandit problems.
A new batch ensemble method reduces regret in stochastic bandits.
problem Efficiently balancing exploration and exploitation in online RL.
method Proposes a batch ensemble scheme to achieve near-optimal regret.
result Proves near-optimal regret with a single parameter independent of variance.
New algorithms improve linear bandit performance with low computation.
problem Optimizing reward in linear stochastic bandits.
method Reward-biased maximum likelihood method modified for linear and generalized linear bandits.
result New policies achieve order-optimality and competitive empirical performance.