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.
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.
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.
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.
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.
Two randomized algorithms improve performance in non-stationary linear bandits.
problem Conservatism in optimistic algorithms for non-stationary linear bandits.
method Two perturbation approaches: randomization and random perturbations.
result D-RandLinUCB and D-LinTS achieve optimal dynamic regret and are oracle-efficient.
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 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.
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.
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.
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.
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.
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.
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 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 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 algorithms for GLMs adapt to non-stationary contexts.
problem Dealing with abrupt changes in non-stationary environments.
method Upper Confidence Bound algorithms using sliding window or discounted maximum-likelihood.
result Theoretical guarantees on dynamic regret of order d^2/3 G^1/3 T^2/3.
An algorithm for efficient experimentation in a dynamic environment with personalized preferences and context drifts.
problem Efficiently recommending decisions to users with personalized preferences in a context where the environment is changing over time.
method Dri-MED, inspired from the linear version of the MED strategy, adapted to handle non-stationary heteroskedastic noise.
result The instance-dependent regret scales as $ ilde{\mathcal O}\left(\fracκ{ ildeΔ}d^2(\log(T)
ight)$ , with i l d e Δ ildeΔ i l d e Δ being the constraint-aware sub-optimality gap. 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.
New algorithm reduces online learning regret by exploiting historical invariances.
problem Stochastic non-stationary linear bandits with changing reward models.
method ISD-linUCB algorithm that learns invariances in reward model.
result Significant regret improvements in fast-changing environments with historical data.
We consider a stochastic linear bandit model in which the available actions correspond to arbitrary context vectors whose associated rewards follow a non-stationary linear regression model. In this setting, the unknown regression parameter is allowed to vary in time. To address this problem, we propose D-LinUCB, a nove…
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 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 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.
A novel algorithm for best-arm identification in non-stationary linear bandits reduces error probability.
problem Non-stationary environments in A/B testing scenarios.
method Proposes a novel algorithm P 1 \mathsf{P1} P1 - R A G E \mathsf{RAGE} RAGE for robust best-arm identification. result Error probability decreases as exp ( − T Δ ( 1 ) 2 / d ) \exp(-TΔ^2_{(1)}/d) exp ( − T Δ ( 1 ) 2 / d ) , demonstrating robustness to non-stationarity. 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.
Algorithm minimizes control regret for non-stationary LQR systems.
problem Control of non-stationary LQR systems with unknown dynamics.
method Adaptive non-stationarity detection and OLS estimator with small bias.
result Achieves optimal dynamic regret of $ ilde{\mathcal{O}}\left(V_T^{2/5}T^{3/5}
ight)$ .
This paper improves recommender systems by handling dynamic user preferences and item popularity.
problem Dynamic user preferences and changing item popularity in recommender systems.
method Developed a Thompson sampling-based policy for a high-dimensional linear bandit problem, reducing feature vector dimensionality and using exponentially increasing weights.
result Proved a regret bound that scales with the reduced dimension, demonstrating effectiveness in trade-off between computational complexity and regret performance.
Decentralized learning for matching markets with time-varying preferences.
problem Matching between competing agents and supply arms with time-varying preferences.
method Linear contextual bandit framework, learning algorithms to identify latent environment and stable matchings.
result Achieve instance-dependent logarithmic regret, applicable for large markets.
Optimistic algorithm reduces regret in non-stationary linear MDPs.
problem Efficient learning in non-stationary linear MDPs with evolving reward and transition.
method OPT-WLSVI, an optimistic model-free algorithm using exponential weights.
result Achieves a regret bound of O ~ ( d 5 / 4 H 2 Δ 1 / 4 K 3 / 4 ) \widetilde{\mathcal{O}}(d^{5/4}H^2 Δ^{1/4} K^{3/4}) O ( d 5/4 H 2 Δ 1/4 K 3/4 ) . 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…
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.
A new method optimizes in nonstationary environments with many arms efficiently.
problem Optimizing in nonstationary environments with a large number of arms.
method Gaussian interpolation to learn continuous Lipschitz reward functions in nonstationary environments.
result Efficiently learns continuous Lipschitz reward functions with O ∗ ( T ) \mathcal{O}^*(\sqrt{T}) O ∗ ( T ) cumulative regret. We extend Bayesian multi-armed bandit (MAB) algorithms beyond their original setting by making use of sequential Monte Carlo (SMC) methods. A MAB is a sequential decision making problem where the goal is to learn a policy that maximizes long term payoff, where only the reward of the executed action is observed. In the …
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. A new algorithm tackles delayed combinatorial semi-bandit with causal relations.
problem Optimizing decisions in a non-stationary environment with delayed and causally related rewards.
method Formalized as a non-stationary delayed combinatorial semi-bandit problem, the approach models causal relations with a directed graph in a stationary structural equation model. The agent learns these relations from delayed feedback to optimize decisions.
result Proved a regret bound for the proposed algorithm's performance.
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. A new framework tunes hyperparameters in real-time for contextual bandits.
problem Optimizing hyperparameters for contextual bandits in real-time.
method CDT (Continuous Dynamic Tuning) framework using Zooming TS algorithm.
result Achieves sublinear regret and performs better than existing methods.
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.