A new algorithm for cryo-EM data collection that balances reward and latency.
problem Optimizing data collection in cryo-EM experiments with action delays.
method Latency-aware contextual bandit framework and COAF algorithm.
result The COAF algorithm efficiently maximizes reward over time in cryo-EM experiments.
New method for online low-rank matrix completion with improved regret.
problem Designing an efficient algorithm for online recommendation systems with low regret.
method Explore-then-commit (ETC) approach and iterative user clustering (OCTAL) for rank-1 setting.
result Nearly optimal regret bounds for online low-rank matrix completion.
Unified approach for conversational recommendation by integrating attributes and items.
problem Cold-start users' real-time personalization in online recommendation.
method Seamlessly unifies attributes and items in Thompson Sampling framework for interactive decision-making.
result Conversational Thompson Sampling (ConTS) outperforms existing methods in success rate and conversation turns.
New MAB model for online caching costs.
problem Learning costs of cached items online.
method Synchronization bandits, MirrorSync algorithm.
result Adversarial regret of O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) for MirrorSync. Two novel methods identify influential features in CMABs for better reward distribution.
problem Suboptimal features degrade rewards, interpretability, and efficiency in CMABs.
method Heterogeneous Incremental Effect (HIE) and Heterogeneous Distribution Divergence (HDD) methods.
result Consistent ability to identify influential HTE features, enhancing CMAB performance.
Algorithm improves online learning in adversarial bandits.
problem Online learning in adversarial multi-armed bandits with non-uniform best arm distribution.
method Online-within-online setup, inner and outer learners, leveraging non-uniform empirical distribution of best arms.
result Improves regret bounds for non-uniform best arm distributions.
PyXAB is a Python library for X-armed bandits and online optimization.
problem Efficiently solving X-armed bandit problems and online blackbox optimization.
method Implementation of 10+ X-armed bandit algorithms and synthetic objectives.
result Evaluation of different algorithms' performance on various synthetic objectives.
A new method approximates deep neural networks using Kalman Filters.
problem Approximating deep neural networks with limited data.
method Matrix Ensemble Kalman Filter-based multi-arm ANN (MEnKF-ANN).
result MEnKF-ANN can adequately approximate LSTM networks and provide uncertainty estimates.
Motivated by problems in search and detection we present a solution to a Combinatorial Multi-Armed Bandit (CMAB) problem with both heavy-tailed reward distributions and a new class of feedback, filtered semibandit feedback. In a CMAB problem an agent pulls a combination of arms from a set { 1 , . . . , k } \{1,...,k\} { 1 , ... , k } in each round, g…
Develops a framework for clustering and distribution matching with bandit feedback.
problem Clustering and distribution matching problems with limited feedback.
method General framework using K K K -armed bandit model, Track-and-Stop method, and Frank--Wolfe algorithm. result Average number of arm pulls matches lower bound, with asymptotic convergence to fundamental limit.
Proposes a fair RMAB framework ensuring equal exposure to arms.
problem Fairness in RMABs where arms are not equally exposed.
method Defines merit of each arm based on stationary reward distribution and ensures equal exposure in proportion to merit.
result Achieves sublinear fairness regret of O ( T ln T ) O(\sqrt{T\ln T}) O ( T ln T ) in single pull case. New policy for non-stationary multi-armed bandits with recovering rewards.
problem Non-stationary multi-armed bandits with recovering rewards.
method Purely Periodic Policies integrating upper confidence bound procedure.
result Approximately O ~ ( N T ) \widetilde{\mathcal O}(N\sqrt{T}) O ( N T ) regret against the offline benchmark. The paper tackles online learning problems with monotone arm sequences, achieving optimal or near-optimal regret bounds.
problem Online learning problems with ordinal and monotone arm sequences, such as dynamic pricing and clinical trials.
method Proposes algorithms for continuum-armed bandit problems with monotone arm sequences, achieving optimal or near-optimal regret bounds.
result Achieves optimal or near-optimal regret bounds for monotone arm sequences, differing from the continuous-armed bandit literature.
Proposes a max-utility arm selection strategy for reducing cumulative regret in sequential query recommendations.
problem Reduces cumulative regret in sequential query recommendations for closed loop interactive learning settings.
method Proposes a max-utility arm selection strategy based on the maximum utility of arms.
result Improves cumulative regret substantially compared to baseline algorithms and random selection.
New algorithm identifies best arm in rested bandit setting.
problem Best arm identification in rested bandit with decreasing losses.
method Introduced a novel best arm identification problem and analyzed an arm elimination algorithm.
result Regret vanishes as time horizon increases, with convergence rate depending on expected loss function.
The paper develops a computational method for efficient online filtering of diffusion processes.
problem Online filtering of discretely observed nonlinear diffusion processes.
method The approach involves Doob's h h h -transforms approximated by solving backward Kolmogorov equations using nonlinear Feynman-Kac formulas and neural networks. result The proposed method can be orders of magnitude more efficient than state-of-the-art particle filters.
Develops Bayesian filtering for online learning and related problems.
problem Sequential machine learning challenges, especially non-stationarity, model misspecification, and high dimensionality.
method Modular adaptive framework, provably robust filter, and sequential parameter updates.
result Improved performance in dynamic, high-dimensional, and misspecified models.
Algorithm selects k arms from context-dependent options using Plackett-Luce model.
problem Selecting k arms from context-dependent options with Plackett-Luce feedback.
method Proposes CPPL algorithm inspired by UCB, evaluated on synthetic and real data.
result Demonstrates effectiveness of CPPL algorithm in online algorithm selection.
Incentive-aware recommender system for online platforms.
problem Myopic agents exploit optimal arms, not exploring alternatives.
method Model as multi-agent bandit problem, incentivizes exploration.
result Asymptotically optimal performance with ex-post fairness.
New algorithm handles bandit problems under translations and scales.
problem Adversarial multi-armed bandit problems with arbitrary translations and scales.
method Innovative online algorithm invariant to translations and scales, using universal prediction.
result Second-order regret bounds, unaffected by affine transformations of losses.
Combines offline and online learning for identifying the best arm in bandits.
problem Identifying the best arm in stochastic bandits with offline data.
method Lower bound analysis and algorithm development for optimal best-arm identification.
result Developed algorithms matching lower bound on sample complexity for small δ.
Online convex optimization is a sequential prediction framework with the goal to track and adapt to the environment through evaluating proper convex loss functions. We study efficient particle filtering methods from the perspective of such a framework. We formulate an efficient particle filtering methods for the non-st…
Anchor-TS uses median anchoring to improve online decision-making from offline data with distribution shift.
problem Improving online decision-making from offline data with distribution shift.
method Sample-Mean Anchored Thompson Sampling (Anchor-TS) with median anchoring.
result Anchor-TS safely leverages offline data to accelerate online learning and reduces regret.
The paper provides tight bounds for improving multi-armed bandits problem.
problem Improving multi-armed bandits problem with concave reward functions.
method Upper and lower bounds for randomized online algorithms, providing an O ( k log k ) O(\sqrt{k} \log k) O ( k log k ) approximation. result Achieved nearly-tight approximation guarantees for the improving multi-armed bandits problem.
Neural Jump ODEs improve online filtering and classification with robust performance.
problem Online filtering and classification in settings with irregular and partial observations.
method Modeling conditional expectation using Neural Jump ODEs, with theoretical convergence guarantees.
result Demonstrated superior performance over classical methods, especially in complex scenarios.
Study on reward poisoning attacks on CMAB, revealing attackability depends on adversary's knowledge.
problem Reward poisoning attacks on Combinatorial Multi-Armed Bandits (CMAB).
method Provided a sufficient and necessary condition for attackability, devised an attack algorithm.
result Attackability of CMAB depends on adversary's knowledge of the bandit instance.
A bandit problem with filtered Poisson process data.
problem Maximizing points revealed from a continuum action space.
method Upper confidence bound algorithm with data-adaptive discretisation.
result Regret bound of O(T^(2/3)) under Lipschitz assumption.
Adaptive and sequential experiment design is a well-studied area in numerous domains. We survey and synthesize the work of the online statistical learning paradigm referred to as multi-armed bandits integrating the existing research as a resource for a certain class of online experiments. We first explore the tradition…
Unified meta algorithms estimate various distribution functionals in infinite-armed bandits.
problem Estimating various distribution functionals in infinite-armed bandits.
method Unified meta algorithms for offline and online settings, achieving optimal sample complexities.
result Online estimation offers significant advantage for certain distribution functionals.
Paper achieves logarithmic regret for online Kalman filter learning.
problem Predicting observations from an unknown, partially observed linear system with stochastic noise.
method Online least-squares algorithm exploiting the approximate linearity of Kalman filter predictions.
result Achieves regret of order poly(log(N)) with high probability.
FPML algorithm reduces regret by limiting the number of arms chosen per round.
problem Adversarial online learning with resource budget constraints.
method Follow the Perturbed Multiple Leaders (FPML) algorithm.
result Achieves expected regret O ( T 1 B + 1 ln ( N ) B B + 1 ) \mathcal{O}(T^{\frac{1}{B+1}}\ln(N)^{\frac{B}{B+1}}) O ( T B + 1 1 ln ( N ) B + 1 B ) . New algorithm improves online decision making by adaptively inferring arm rewards.
problem Adaptive selection of arms in MAB leads to non-iid data, complicating accurate inference.
method Proposes a doubly adaptive TS algorithm that leverages causal inference for adaptive reweighting.
result Demonstrates superior empirical performance in identifying the best arm compared to UCB and TS.
Paper optimizes clustering with bandit feedback, reducing errors.
problem Online clustering with bandit feedback, minimizing errors.
method Instance-dependent information-theoretic lower bound, BOC algorithm with adaptive stopping rule.
result BOC algorithm matches lower bound asymptotically and significantly outperforms non-adaptive baseline.
New algorithm optimizes long-term user satisfaction in recommendation systems.
problem Optimizing long-term user satisfaction in recommendation systems with delayed rewards.
method Developed a predictive model of delayed rewards and a bandit algorithm that balances exploration and exploitation.
result Our approach results in substantially better performance compared to short-term or delayed optimization.
We consider a problem of stochastic online learning with general probabilistic graph feedback, where each directed edge in the feedback graph has probability p i j p_{ij} p ij . Two cases are covered. (a) The one-step case, where after playing arm i i i the learner observes a sample reward feedback of arm j j j with independent prob…
AUCRSS detects change points in partially observed multivariate autocorrelated data.
problem Detecting change points in multivariate autocorrelated data with limited sensing resources.
method Adaptive Upper Confidence Region (AUCRSS) with state space model (SSM), adaptive sampling policy, and generalized likelihood ratio test.
result The method outperforms existing approaches in detecting change points efficiently.
Proposes Genetic Thompson Sampling for multi-armed bandits, improving performance in nonstationary settings.
problem Improving sequential decision making tasks of online learning agents using multi-armed bandits.
method Integrates genetic principles into Thompson Sampling for multi-armed bandits.
result Significantly outperforms baselines in nonstationary settings.
New algorithm identifies best arm in rare event scenarios.
problem Identifying the best arm with tiny reward probability.
method Approximated Compound Poisson process for faster algorithms.
result Improved computational efficiency with minor sample complexity increase.
New model tackles interference in online experiments.
problem Understanding cumulative performance in interference experiments.
method Introduces Multi-Armed Bandits with Interference (MABI) model.
result Cluster randomization policy achieves optimal expected regret and high probability bound.
A new algorithm for resource-aware multi-armed bandits minimizes regret.
problem Optimizing resource usage in a multi-armed bandit problem with censored observations.
method UCB-inspired online learning algorithm with theoretical regret analysis.
result The proposed algorithm outperforms standard multi-armed bandit algorithms in simulations.
Robust Kalman filtering method for outlier detection.
problem Outliers and misspecified measurement models in state-space models.
method Combines generalised Bayesian inference with Kalman filters for robustness and efficiency.
result Matches or outperforms other robust filtering methods at lower computational cost.
New approach to multi-armed bandit problem aims to maximize highest total reward.
problem Traditional multi-armed bandit problem objective of maximizing total reward is not suitable in certain applications.
method Adaptive explore-then-commit policy with confidence bounds and adaptive stopping criterion.
result Achieves asymptotic and worst-case regret bounds for the new objective.
New method for contextual bandits with corrupted context.
problem Contextual bandits with corrupted context in online settings.
method Combining contextual bandit and multi-armed bandit approaches.
result Improved learning from all iterations, including corrupted ones.
Improved real-time UAV terrain following with RVM-RLS filter.
problem Accurate real-time waypoints estimation under measurement noise in nonlinear, time-varying systems.
method Residual Variance Matching Recursive Least Squares (RVM-RLS) filter guided by RVME criterion.
result Improved waypoints estimation accuracy by approximately 88% compared to benchmarks.
New algorithm for shareable arms with load-dependent rewards in stochastic bandits.
problem Learning optimal play strategy with shareable finite-capacity arms in stochastic bandits.
method Developed a capacity estimator and online learning algorithm for MP-MAB with shareable arms.
result Regret upper bound matches the lower bound, validating the algorithm's performance.
LatentTrack generates model parameters online for nonstationary data.
problem Online probabilistic prediction under nonstationary dynamics.
method Sequential neural architecture with latent filtering and amortized inference.
result Consistently lower negative log-likelihood and mean squared error than baselines.
A new algorithm learns optimal source placement in large networks.
problem Optimizing source placement in large scale networks with unknown processes.
method Graph-Kernel Multi-Armed Bandit (Grab-UCB) algorithm with adaptive graph dictionary model.
result Online learning algorithm outperforms offline methods in terms of cumulative regret, sample efficiency, and computational complexity.
Ensemble Kalman Filter improves GPSSM inference for online learning.
problem Non-mean-field variational inference issues in GPSSM.
method Combining EnKF with NMF variational inference.
result Improved online learning performance and data-fitting accuracy.