New definition resolves ambiguity in non-stationary bandit classification.
problem Ambiguity in classifying non-stationary bandits using existing definitions.
method Introducing a formal definition that resolves ambiguity and provides a unified approach.
result Unified approach applicable to both Bayesian and frequentist formulations, resolves classification issues.
Unified approach for non-stationary and clustered bandits.
problem Solving non-stationary and clustered bandits with overlapping solutions.
method Test of homogeneity for seamless integration of non-stationary and clustered bandits.
result Unified solution framework for change detection and cluster identification.
Proposes a new algorithm for non-stationary bandits.
problem Non-stationary reward distributions in contextual bandits.
method Multiscale changepoint detection for adaptive learning.
result Regret bound analysis and superior performance in experiments.
Algorithm adapts to non-stationary rewards without prior knowledge.
problem Optimizing decisions in non-stationary environments without prior knowledge of changes.
method Optimization-based algorithm that restarts when non-stationarity is detected.
result Achieves tighter dynamic regret bound and is nearly minimax optimal.
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.
Predictive sampling improves on Thompson sampling for non-stationary bandit environments.
problem Thompson sampling fails in non-stationary bandit environments.
method Proposes predictive sampling, which deprioritizes actions based on information loss rate.
result Predictive sampling outperforms Thompson sampling in all tested non-stationary environments.
New algorithm for non-stationary bandits with slow drifts.
problem Minimizing dynamic regret in non-stationary bandits with slowly varying rewards.
method Extends Successive Elimination to non-stationary bandits with a novel gap profile characterization.
result First instance-dependent regret upper bound for slowly varying non-stationary bandits.
Paper tackles non-stationary kernelized bandits with near-optimal algorithm.
problem Minimizing regret in a time-varying reward function.
method Near-optimal algorithm with a novel restarting phased elimination with random permutation (R-PERP).
result Regret upper bound matches the lower bound, making the algorithm near-optimal.
Algorithm reduces regret in non-stationary bandits and meta-learning with optimal arms.
problem Sequential decision-making with changing task boundaries and optimal arms.
method Reduction to bandit submodular maximization, meta-learning algorithms.
result Regret bounds for both non-stationary and bandit meta-learning problems.
Algorithm minimizes regret in non-stationary dueling bandits with unknown parameters.
problem Minimizing regret in dueling bandits with time-varying preferences.
method Proposes Beat the Winner Reset algorithm and meta-algorithms DETECT and Monitored Dueling Bandits.
result Proves bounds on expected weak and strong regret for non-stationary dueling bandits.
This paper refines the weighted strategy for non-stationary parametric bandits, improving regret bounds.
problem Non-stationary environments with gradual drifting patterns.
method Refined analysis framework for the weighted strategy in linear and generalized linear bandits.
result A simpler weight-based algorithm with improved regret bounds compared to previous studies.
This paper refines the weighted strategy for non-stationary parametric bandits and MDPs, improving regret bounds.
problem Non-stationary environments with gradual drifting patterns.
method Refined analysis framework for the weighted strategy, leading to simpler and more efficient algorithms.
result Improved regret bounds for linear bandits, generalized linear bandits, and self-concordant bandits.
DAL enhances black-box bandit algorithms for non-stationary environments.
problem Non-stationary environments in bandit problems.
method DAL combines any stationary bandit algorithm with a change detector.
result DAL consistently outperforms state-of-the-art methods in various non-stationary scenarios.
Paper tackles non-stationary bandits with various examples.
problem Non-stationary stochastic bandit problem with specific cases.
method Proposes a single algorithm for multiple non-stationary bandit problems.
result Unified solution for four different bandit problems.
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.
Proposes a new TS algorithm for non-stationary bandits using KS tests.
problem Non-stationary multi-armed bandit problems.
method Active detection of change points using KS tests and adaptive Thompson Sampling.
result Sub-linear regret demonstrated for the two-armed bandit case.
Non-stationarity appears in many online applications such as web search and advertising. In this paper, we study the online learning to rank problem in a non-stationary environment where user preferences change abruptly at an unknown moment in time. We consider the problem of identifying the K most attractive items and…
Study MNL-Bandit in non-stationary settings with optimal regret bound.
problem Optimizing decisions in a non-stationary environment for multi-armed bandit problems.
method Develops an algorithm with worst-case expected regret bound and introduces new techniques to handle non-stationarity.
result Optimal regret bound proven for the MNL-Bandit problem in non-stationary environments.
New algorithms reduce regret in non-stationary bandits with increasing payoffs.
problem Non-stationary bandits with monotonically increasing payoffs.
method R-ed-UCB for rested case and R-less-UCB for restless case.
result Regret bound of O ~ ( T 2 3 ) \widetilde{\mathcal{O}}(T^{\frac{2}{3}}) O ( T 3 2 ) under certain conditions. Novel Bayesian approach for non-stationary linear contextual bandits.
problem Non-stationary linear contextual bandits.
method Weighted Sequential Bayesian (WSB) inference.
result Established frequentist regret guarantees for new algorithms.
Paper introduces Decentralized Non-stationary Competing Bandits ( exttt{DNCB}) for dynamic matching markets.
problem Understanding dynamic two-sided matching markets with competing agents.
method Proposes a decentralized asynchronous learning algorithm ( exttt{DNCB}) for non-stationary environments.
result Obtains sub-linear (logarithmic) regret of exttt{DNCB} in dynamic settings.
Improved algorithm for adaptive dueling bandits with near-optimal regret bound.
problem Non-stationary dueling bandits with unknown number of preference changes.
method Elimination-based rescheduling algorithm for adaptive dynamic regret.
result Near-optimal i l d e O ( S e x t t t C W T ) ilde{O}(\sqrt{S^{ exttt{CW}} T}) i l d e O ( S e x ttt C W T ) dynamic regret bound. New method reduces dynamic regret for non-stationary bandits.
problem Non-stationary stochastic multi-armed bandit problem with changing optimal arm.
method Proposes a method achieving near-optimal dynamic regret without prior knowledge of changes.
result Achieves O ~ ( K N ( S + 1 ) ) \widetilde O(\sqrt{K N(S+1)}) O ( K N ( S + 1 ) ) dynamic regret. New algorithm reduces dynamic regret without prior function change knowledge.
problem Non-stationary stochastic optimization with bandit feedback.
method Fixed step sizes combined with multi-scale sampling framework.
result Achieves optimal dynamic regret without prior function change knowledge.
Paper introduces novel Bandit algorithms for non-stationary environments in finance.
problem Non-stationary reward distributions in financial markets.
method Introduces Adaptive Discounted Thompson Sampling (ADTS) and Combinatorial Adaptive Discounted Thompson Sampling (CADTS) for non-stationary environments in portfolio optimization.
result Bandit Networks improve portfolio optimization performance by 20% compared to classical models.
New algorithm optimizes resource allocation in non-stationary networks.
problem Optimal resource allocation in non-stationary RMABs is computationally hard.
method Sliding-Window Online Whittle (SW-Whittle) policy for non-stationary transition kernels.
result Sub-linear dynamic regret achieved with unknown variation budget.
New approach limits regret in non-stationary bandits.
problem Understanding worst case regret in time-varying bandits.
method Belief inertia argument to resist new evidence after changes.
result Linear worst case regret for classical and restarting algorithms.
Study tackles non-stationary bandit convex optimization with new algorithms.
problem Minimizing regret in non-stationary environments with various measures of non-stationarity.
method Proposed Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE) for strongly convex losses and clipped Exploration by Optimization (cExO) for general convex losses.
result Proved minimax-optimality of TEWA-SE for strongly convex losses and introduced cExO for general convex losses.
DS-TS adapts to abrupt and smooth changes in bandit problems.
problem Non-stationary multi-armed bandit problems with abrupt and smooth changes.
method Discounted Thompson Sampling with Gaussian priors.
result Achieves nearly optimal regret bound for both abrupt and smooth changes.
Study non-stationary bandits with resource constraints.
problem Maximize reward in a non-stationary environment with resource constraints.
method Propose new non-stationarity measure and use primal-dual analysis.
result Upper and lower bounds for non-stationary BwK problem.
New algorithm tracks changes in infinite action space rewards.
problem Non-stationary Lipschitz bandits with infinite actions.
method Adaptive tracking of significant shifts using hierarchical discretization.
result Achieves minimax-optimal dynamic regret bound of O ~ ( i l d e L 1 / 3 T 2 / 3 ) \mathcal{\widetilde{O}}( ilde{L}^{1/3}T^{2/3}) O ( i l d e L 1/3 T 2/3 ) . Most contextual bandit algorithms minimize regret against the best fixed policy, a questionable benchmark for non-stationary environments that are ubiquitous in applications. In this work, we develop several efficient contextual bandit algorithms for non-stationary environments by equipping existing methods for i.i.d. …
Adaptive smooth non-stationary bandits achieve optimal regret rates without knowing parameters.
problem Smooth non-stationary bandits with Hölder class rewards.
method Established optimal dynamic regret rate and adaptive algorithm.
result Optimal dynamic regret can be attained adaptively without knowing Hölder exponent and coefficient.
New GLB algorithm reduces regret in non-stationary settings.
problem Non-stationary environments in GLBs.
method Adapted projection step for tracking parameter-drift.
result Regret bound of i l d e O ( B T 1 / 3 T 2 / 3 ) ilde{\mathcal{O}}(B_T^{1/3}T^{2/3}) i l d e O ( B T 1/3 T 2/3 ) under geometric action set. New algorithm tackles non-stationary combinatorial semi-bandit problems with optimal regret bounds.
problem Non-stationary combinatorial semi-bandit problems in switching and dynamic environments.
method Developed algorithms for both switching and dynamic cases, achieving nearly optimal regret bounds.
result Achieved nearly optimal regret bounds in both switching and dynamic cases.
New approach turns optimal stationary RL into non-stationary RL without prior knowledge.
problem Optimal RL in non-stationary environments without prior knowledge of non-stationarity.
method Black-box reduction of optimal stationary RL algorithms to non-stationary RL.
result Achieves optimal dynamic regret bounds in various RL settings.
New algorithm tackles non-stationary delayed feedback in recommender systems.
problem Challenges in learning from delayed feedback in non-stationary environments.
method Developed a UCRL-based algorithm for non-stationary, delayed bandits with intermediate observations.
result Sublinear regret guarantees for the proposed algorithm in non-stationary delayed environments.
Paper designs a bandit algorithm without reward distribution info.
problem Designing bandit algorithms without reward distribution info.
method Alternates between greedy rule and forced exploration.
result Achieves substantial regret upper bounds.
We consider the multi armed bandit problem in non-stationary environments. Based on the Bayesian method, we propose a variant of Thompson Sampling which can be used in both rested and restless bandit scenarios. Applying discounting to the parameters of prior distribution, we describe a way to systematically reduce the …
New GLB algorithm handles non-stationary data with forgetting.
problem Non-stationary GLB with non-convex projection or burn-in phases.
method Self-concordant GLB with sliding window or exponential weights for forgetting.
result Novel confidence-based algorithm for maximum likelihood estimator.
A survey is performed of various Multi-Armed Bandit (MAB) strategies in order to examine their performance in circumstances exhibiting non-stationary stochastic reward functions in conjunction with delayed feedback. We run several MAB simulations to simulate an online eCommerce platform for grocery pick up, optimizing …
New algorithm identifies best arm in non-stationary linear bandits with improved complexity.
problem Best arm identification in non-stationary linear bandits with adversarial parameters.
method Proposed Adjacent-optimal design and e x t s f A d j a c e n t − B A I extsf{Adjacent-BAI} e x t s f A d j a ce n t − B A I algorithm. result Error probability matches arm-set-dependent lower bound up to constants.
RAVEN-UCB addresses non-stationary MAB problems with tighter regret bounds.
problem Non-stationary environments in multi-armed bandits.
method Combines variance-aware adaptation with three innovations: confidence bounds, adaptive control, and recursive updates.
result Achieves tighter regret bounds than UCB1 and UCB-V.
We introduce GLR-klUCB, a novel algorithm for the piecewise iid non-stationary bandit problem with bounded rewards. This algorithm combines an efficient bandit algorithm, kl-UCB, with an efficient, parameter-free, changepoint detector, the Bernoulli Generalized Likelihood Ratio Test, for which we provide new theoretica…
Observer learns optimal policy from learner's actions without rewards.
problem Learning optimal policy from non-rewarded actions of a non-stationary learner.
method Two-Phase Suffix Imitation framework.
result Observer achieves convergence rate of O ~ ( 1 / N ) \tilde O(1/\sqrt{N}) O ~ ( 1/ N ) . New method optimizes policies in non-stationary environments.
problem Optimizing policies in non-stationary, context-dependent environments.
method Two-phase approach: offline learning and online adaptation.
result Our method outperforms existing approaches in both synthetic and real-world datasets.
Paper establishes lower bounds for non-stationary kernelized bandits.
problem Optimizing functions with noisy observations in non-stationary scenarios.
method Develops algorithm-independent lower bounds for time-varying functions under total variation constraints.
result First algorithm-independent lower bounds for time-varying kernelized bandits.
Improved GP bandit algorithms for noiseless, varying noise, and RKHS norms.
problem Minimizing regret in Gaussian process bandits with unknown reward functions.
method New upper bound on maximum posterior variance, refined MVR and PE algorithms.
result Optimal regret bounds for noiseless, varying noise, and RKHS norms.