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 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.
Bayesian metalearning improves performance in linear bandits with misspecified priors.
problem Improper priors lead to suboptimal performance in sequential decision-making.
method Proves performance bounds for metalearning priors in stochastic linear bandits and develops a metalearning algorithm.
result Metalearning can improve performance by learning the prior from multiple tasks.
New algorithm optimizes smooth functions with Hölder exponent > 1.
problem Optimizing smooth functions with unknown Hölder exponent > 1.
method Two-layer algorithms using misspecified linear/polynomial bandit algorithms in bins.
result Regret bound of O ~ ( T d + α d + 2 α ) \tilde{O}(T^{\frac{d+\alpha}{d+2\alpha}}) O ~ ( T d + 2 α d + α ) for α > 1 \alpha > 1 α > 1 . Improved algorithm for misspecified MLMDPs with bounded regret and space/time complexities.
problem Misspecified linear Markov decision processes.
method Proposes an algorithm with three desirable properties: bounded regret, bounded space/time complexities, and no need for misspecification input.
result Regret scales as K max { ε e x t m i s , ε e x t t o l } K \max \{ \varepsilon_{ ext{mis}}, \varepsilon_{ ext{tol}} \} K max { ε e x t mi s , ε e x t t o l } , improving existing bounds. New algorithms for best arm identification in bandits robust to misspecified parameters.
problem Inconsistent learning performance of traditional MAB algorithms when parameters are misspecified.
method Proposes two classes of asymptotically near-optimal algorithms for statistically robust MAB under fixed-budget pure exploration.
result Establishes fundamental performance limits and proposes algorithms that are asymptotically near-optimal.
Algorithm reduces regret in misspecified linear contextual bandits.
problem Misspecified linear contextual bandits with bounded misspecification.
method Data selection scheme for online regression, leveraging uncertainty.
result Regret bound of O ~ ( d 2 / Δ ) \tilde O(d^2/Δ) O ~ ( d 2 /Δ ) when ζ ≤ O ~ ( Δ / d ) ζ \leq \tilde O(Δ/\sqrt{d}) ζ ≤ O ~ ( Δ/ d ) . 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 ) . Statistical inference for misspecified contextual bandits is challenging due to adaptivity issues.
problem Statistical inference for misspecified contextual bandits
method Inverse-probability-weighted Z-estimation framework
result Consistent and asymptotically normal estimator with sandwich variance estimator
New algorithms for optimizing functions with noisy feedback, even when the model is misspecified.
problem Optimizing a black-box function with noisy bandit feedback, especially when the model is misspecified.
method Developed two algorithms based on Gaussian process methods: EC-GP-UCB and Phased GP Uncertainty Sampling.
result Achieved optimal dependence on misspecification error without prior knowledge, and effective in stochastic contextual settings.
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.
Gaussian prior and likelihood improve bandit learning performance.
problem Improving bandit learning with misspecified Gaussian distributions.
method An agent with a bounded information ratio interacts with a Bernoulli bandit based on a Gaussian prior and likelihood.
result The regret increase is at most linear in the square-root of the time horizon for diffuse distributions.
LinFACT identifies all ε-best arms in linear bandits with near-optimal efficiency.
problem Efficiently identifying multiple optimal candidates in high trial-and-error cost tasks.
method LinFACT algorithm designed for linear bandits, with information-theoretic lower bound and upper bound derivation integration.
result LinFACT achieves instance optimality, matching lower bound up to a logarithmic factor.
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. Adaptive inference for M M M -estimators in bandit data with model misspecification.
problem Challenges in off-policy inference for adaptively collected bandit data with a misspecified model.
method A novel approach to define a projected solution over a stationary evaluation policy, stabilizing variance with flexible methods.
result Valid inference for M M M -estimators in adaptive settings, even with unstable treatment policies. Improved guarantees for misspecified kernelized bandit optimization.
problem Misspecification in kernelized bandit optimization.
method Localization and domain splitting techniques.
result Logarithmic or polylogarithmic growth of misspecification amplification.
Bayesian algorithms perform well even with misspecified priors, especially in meta-learning.
problem Performance degradation of Bayesian algorithms with misspecified priors.
method Thompson sampling and meta-learning analysis with misspecified priors.
result Thompson sampling's performance degrades gracefully with misspecification, with a bound of i l d e O ( H 2 ε ) ilde{\mathcal{O}}(H^2 ε) i l d e O ( H 2 ε ) . The paper addresses statistical inference for online decision-making in a contextual bandit setting.
problem Understanding the performance of reward models in online decision-making with contextual information.
method The paper uses the contextual bandit framework with a linear reward model and the ε \varepsilon ε -greedy policy to address the exploration-exploitation dilemma. It employs the martingale central limit theorem and inverse propensity score weighting to establish asymptotic normality of parameter estimators. result The online ordinary least squares estimator and the online weighted least squares estimator are asymptotically normal, providing insights into the performance of the reward model.
New algorithms adapt to model misspecification in contextual bandits.
problem Design efficient algorithms for contextual bandits that handle model misspecification gracefully.
method Oracle-efficient algorithms for ε-misspecified contextual bandits using square loss regression.
result First algorithm achieving optimal regret bound for unknown misspecification level in linear contextual bandits.
The paper improves bandit algorithms by incorporating random-effect models.
problem Improving statistical efficiency in multi-armed bandit problems with misspecified priors.
method Introduces a random-effect model to bandits, estimating arm means and designing a UCB algorithm ReUCB.
result Derives an upper bound on the Bayes regret of ReUCB, showing improved performance over Thompson sampling.
Efficient algorithms for low-rank bandits using subspace recovery.
problem Contextual bandits with low-rank reward matrices.
method Spectral methods for subspace recovery, reformulating as linear bandits.
result Nearly optimal policy evaluation and best policy identification, minimax guarantees for regret minimization.
Bayesian bandits misspecification affects UX optimization, revealing new models.
problem Misspecification of value models in Bayesian bandits impacts UX optimization.
method Formulated UXO as a restless, sleeping bandit with unobserved confounders and optional stopping. Provided model extensions to address misspecifications.
result Common misspecifications lead to sub-optimal rewards, demonstrating overdispersion's effects on bandit performance.
Study on adaptivity to kernel regularity in bandit problems.
problem Adaptation to unknown kernel regularity in continuum-armed bandit problems.
method Derive adaptivity lower bound and verify with minimax non-adaptive kernelised bandit algorithms.
result Impossibility of achieving optimal cumulative regret in different RKHSs with varying regularities.
Paper presents a machine learning method to improve significance tests for misspecified linear models.
problem Misspecification of linear assumptions in social science models leads to inaccurate significance levels.
method Apply machine learning to fit ground truth function, calculate linear approximation, and adjust the estimator.
result The method significantly outperforms linear regression for non-linear ground truth functions.
Plug-in method improves performative prediction accuracy.
problem Learning under performative feedback with slow convergence rates.
method Plug-in performative optimization using models.
result Plug-in method can be superior to model-agnostic strategies.
Thompson sampling provides a solution to bandit problems in which new observations are allocated to arms with the posterior probability that an arm is optimal. While sometimes easy to implement and asymptotically optimal, Thompson sampling can be computationally demanding in large scale bandit problems, and its perform…
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.
Framework predicts responses in misspecified systems using GPLFM and BNNs.
problem Predicting responses in dynamical systems with model misspecification.
method Integrates GPLFM and BNNs for uncertainty-aware inference and prediction.
result Systematic propagation of uncertainty from diagnosis to prediction.
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.
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.
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.
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.
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. 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.
This article introduces the concepts around Online Bandit Linear Optimization and explores an efficient setup called SCRiBLe (Self-Concordant Regularization in Bandit Learning) created by Abernethy et. al.\cite{abernethy}. The SCRiBLe setup and algorithm yield a O ( T ) O(\sqrt{T}) O ( T ) regret bound and polynomial run time comple…
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.