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.
Bayesian optimization improved for biased data.
problem Adversarial bias in observations, especially hidden confounders.
method Reduction to dueling bandits, information-directed sampling (IDS).
result First efficient kernelized algorithm with regret guarantees.
The paper tackles fair sequential decision making with biased linear bandit feedback.
problem Fair sequential decision making with biased linear bandit feedback.
method Phased elimination algorithm to correct unfair evaluations, establishing upper bounds on regret.
result The worst-case regret is smaller than O ( κ ∗ 1 / 3 log ( T ) 1 / 3 T 2 / 3 ) \mathcal{O}(κ_*^{1/3}\log(T)^{1/3}T^{2/3}) O ( κ ∗ 1/3 log ( T ) 1/3 T 2/3 ) . The paper tackles bandit problems with biased offline data by using causal methods.
problem Improving bandit algorithms with biased offline data that includes confounding and selection biases.
method Formalizes the problem from a causal perspective, categorizes biases, and derives robust bounds for each arm.
result Causal bounds can guide the bandit agent to learn a nearly-optimal decision policy and consistently reduce asymptotic regret.
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.
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. 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.
LinUCB algorithm handles adaptive sampling biases for linear bandits.
problem Adaptive sampling introduces biases in statistical inference.
method LinUCB algorithm with stability property for linear bandits.
result LinUCB achieves asymptotic normality with Wald-type confidence sets.
In a linear stochastic bandit model, each arm is a vector in an Euclidean space and the observed return at each time step is an unknown linear function of the chosen arm at that time step. In this paper, we investigate the problem of learning the best arm in a linear stochastic bandit model, where each arm's expected r…
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…
The paper tackles noisy multi-armed bandit problems with improved regret guarantees.
problem Tackling noisy evaluations in multi-armed bandit problems.
method Derives different algorithmic approaches and theoretical guarantees based on the type of observation functions.
result Improved regret guarantees for noisy linear functions of true rewards.
A new strategy for identifying the best arm in Gaussian bandits with improved exploration.
problem Best-arm identification for Gaussian bandits with bounded means and unit variance.
method Exploration-Biased Sampling, a non-asymptotic approach with improved exploration behavior.
result Improved exploration behavior makes the strategy more stable and interpretable.
Study incentivizes exploration in non-stationary MAB with compensation.
problem Incentivized exploration for non-stationary stochastic bandits with biased feedback.
method Proposed algorithms for abruptly-changing and continuously-changing non-stationary environments.
result Achieves sublinear regret and compensation over time.
Inspired by the Reward-Biased Maximum Likelihood Estimate method of adaptive control, we propose RBMLE -- a novel family of learning algorithms for stochastic multi-armed bandits (SMABs). For a broad range of SMABs including both the parametric Exponential Family as well as the non-parametric sub-Gaussian/Exponential f…
Study contextual online pricing with biased offline data, achieving optimal regret bounds.
problem Contextual online pricing with biased offline data.
method Identify δ 2 δ^2 δ 2 to measure data bias, use OFU policy and robust variant for unknown bias. result Achieve minimax-optimal regret bounds for contextual pricing.
New ranking algorithms improve online content delivery by learning from click data.
problem Bias in ranking systems due to production system biases.
method Proposed novel extensions of LinUCB and Linear Thompson Sampling algorithms to handle position-based click model.
result Validated the proposed algorithms through offline and online experiments.
Paper tackles dueling bandits with delayed feedback, revealing preference bias.
problem Real-world dueling bandit applications often face delays in feedback.
method Introduces biased dueling bandit problem with stochastic delayed feedback, presents two algorithms.
result Two algorithms achieve optimal regret bounds for dueling bandit problems with delay.
Contextual bandits have the same exploration-exploitation trade-off as standard multi-armed bandits. On adding positive externalities that decay with time, this problem becomes much more difficult as wrong decisions at the start are hard to recover from. We explore existing policies in this setting and highlight their …
New algorithms handle missing outcomes in MAB, reducing regret.
problem Missing outcomes in real-world MAB scenarios lead to biased estimates and linear regret.
method Introduced algorithms for MAR and MNAR missingness mechanisms in MAB.
result Significant improvements in decision-making by accounting for missingness.
New method uses offline data to improve online bandit learning, even when distributions differ.
problem Improving online bandit learning with different offline and online distributions.
method MIN-UCB policy that adapts to offline data when informative, achieving tight regret bounds.
result MIN-UCB policy outperforms UCB policy with offline data and provides tight regret bounds.
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.
New approach for online learning with adaptive adversaries, simpler and more effective.
problem Online learning with adaptive adversaries, especially in bandits and MDPs.
method Uses standard unbiased estimators and a simple increasing learning rate schedule, aided by logarithmically homogeneous self-concordant barriers and strengthened Freedman's inequality.
result First high-probability regret bounds for adversarial bandits and MDPs, resolving open problems.
New algorithm mitigates affinity bias in hiring feedback loops.
problem Mitigating affinity bias in hiring decisions to avoid unconscious favoritism.
method Introducing affinity bandits, a new bandit variant that accounts for evolving biased feedback.
result Elimination-style algorithm nearly matches the derived regret bound, outperforming classical algorithms.
This paper tackles bandit optimization with a new pairwise comparison oracle for unknown strongly concave functions.
problem Maximizing an unknown strongly concave function over T periods with a biased pairwise comparison oracle.
method Introduced a discretization technique and local polynomial approximation to relate the problem to linear bandits. Developed a tournament successive elimination technique to localize the discretized cell and run LinUCB algorithm on cells.
result Established optimal regret bounds and improved state-of-the-art results in operations management problems.
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.
Paper tackles LDP bandits learning with improved results and sub-linear regret.
problem Contextual bandits learning with LDP privacy constraints.
method Simple black-box reduction frameworks for context-free bandits, extended to GLB.
result First result for BCO with multi-point feedback under LDP, sub-linear regret for GLB.
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.
Study non-linear combinatorial bandits with polynomial rewards, finding significant differences from linear cases.
problem Adversarial combinatorial bandits with general non-linear reward functions.
method Extending existing work on adversarial linear combinatorial bandits, analyzing minimax optimal regret for polynomial and non-polynomial reward functions.
result Minimax optimal regret bounds for adversarial combinatorial bandits with general non-linear reward functions.
Estimators computed from adaptively collected data do not behave like their non-adaptive brethren. Rather, the sequential dependence of the collection policy can lead to severe distributional biases that persist even in the infinite data limit. We develop a general method -- W \mathbf{W} W -decorrelation -- for transformi…
Unified approach for non-stationary linear bandits with dynamic regret.
problem Non-stationary linear bandits with round-specific feasible actions and drifting reward models.
method Unified misspecification-reduction viewpoint, restarting algorithms with misspecification-dependent regret guarantees.
result Optimal \(T^{2/3}P_T^{1/3}\) dynamic-regret dependence for both linear bandits and contextual linear bandits.
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 method reduces bias in learning from large action spaces using selective importance sampling.
problem Learning from large-scale recommendation systems with bandit feedback and supervised labels.
method Selective Importance Sampling (sIS) and Policy Optimization for eXtreme Models (POXM) algorithm.
result POXM method significantly outperforms existing methods in learning from bandit feedback on XMC tasks.
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.
Optimizes pure exploration in linear bandits with a new algorithm.
problem Best-arm identification in linear stochastic bandits.
method Developed the first asymptotically optimal algorithm for fixed-confidence pure exploration in linear bandits.
result Avoids the pitfall of a simple but difficult instance and bypasses the need to solve an optimal design problem.
New approach reduces unconstrained linear bandits to simpler optimization problems.
problem Unconstrained linear bandits problem.
method Perturbation-based approach combined with comparator-adaptive OLO algorithms.
result First high-probability guarantees for both static and dynamic regret in unconstrained linear 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. Randomized exploration in linear bandits achieves optimal regret bounds.
problem Optimizing exploration in high-dimensional linear bandit problems.
method Analysis of Thompson sampling without forced optimism.
result Randomized exploration algorithms achieve an O ( d n log ( n ) ) O(d\sqrt{n} \log(n)) O ( d n log ( n )) regret bound in smooth, strongly convex action spaces. New algorithm for partially observable contexts in finance.
problem Decision making based on partially observable, correlated market information.
method EMKF-Bandit algorithm integrating system identification, filtering, and bandit algorithms.
result Sub-linear regret under conditions on filtering.
Algorithm balances online and offline data for linear bandits.
problem Online learning with an offline dataset in linear bandits.
method Proposes a linear bandit algorithm that uses offline data early and increasingly favors exploration as the horizon grows.
result Establishes regret bounds showing competitive performance with both purely online and offline solutions.
A new algorithm for conversational recommendation systems using dueling bandits in GLMs.
problem Limited user feedback in existing conversational bandit methods.
method Integrates dueling bandits with relative feedback in generalized linear models.
result Theoretical and empirical validation of ConDuel's efficacy.
The paper tightens the regret rate for linear bandit problems.
problem Bayesian regret in linear bandit problems.
method Information-theoretic framework and chaining argument.
result Established a new bound with a tight rate of O ( d T ) O(d\sqrt{T}) O ( d T ) . Modified Meta-TS for linear contextual bandits reduces regret.
problem Optimizing decision-making in dynamic environments with context vectors.
method Meta-TSLB algorithm for linear contextual bandits, analyzing Bayes regret.
result Derives an O ( ( m + log ( m ) ) n log ( n ) ) O((m+\log(m))\sqrt{n\log(n)}) O (( m + log ( m )) n log ( n ) ) bound on Bayes regret. 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.
New BO method optimizes functions efficiently even with unknown hyperparameters.
problem Inaccurate estimation of Gaussian process hyperparameters degrades BO performance.
method Exploits multi-armed bandit and novel training loss function for consistent hyperparameter estimation.
result Sub-linear convergence to global optimum with unknown hyperparameters.
New meta-learning approach for bandit policies that achieve high average reward.
problem Designing bandit policies that balance between worst-case and Bayesian assumptions.
method Differentiable parameterized policies optimized using policy gradients.
result Proposed algorithm achieves low regret and is practical for various bandit problems.
New algorithms minimize regret in multi-task and lifelong linear bandits with shared representation.
problem Minimizing regret in multi-task and lifelong linear bandits with shared representation.
method Novel algorithms using efficient estimator for low-rank linear feature extractor and novel analysis.
result Achieved regret bounds matching minimax lower bound up to logarithmic factors.
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.