Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels

• URL: http://arxiv.org/abs/2506.18186v2
• Date: Sun, 19 Oct 2025 18:24:22 GMT
• Title: Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels
• Authors: Md Kamran Chowdhury Shisher, Vishrant Tripathi, Mung Chiang, Christopher G. Brinton,
• Abstract summary: We study optimal resource allocation in restless multi-armed bandits (RMABs) under unknown and non-stationary dynamics.<n>We propose a Sliding-Window Online Whittle (SW-Whittle) policy that remains computationally efficient while adapting to time-varying kernels.<n>Our algorithm consistently outperforms baselines, achieving the lowest cumulative regret across a range of non-stationary environments.
• Score: 24.314013749328677
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study optimal resource allocation in restless multi-armed bandits (RMABs) under unknown and non-stationary dynamics. Solving RMABs optimally is PSPACE-hard even with full knowledge of model parameters, and while the Whittle index policy offers asymptotic optimality with low computational cost, it requires access to stationary transition kernels - an unrealistic assumption in many applications. To address this challenge, we propose a Sliding-Window Online Whittle (SW-Whittle) policy that remains computationally efficient while adapting to time-varying kernels. Our algorithm achieves a dynamic regret of $\tilde O(T^{2/3}\tilde V^{1/3}+T^{4/5})$ for large RMABs, where $T$ is the number of episodes and $\tilde V$ is the total variation distance between consecutive transition kernels. Importantly, we handle the challenging case where the variation budget is unknown in advance by combining a Bandit-over-Bandit framework with our sliding-window design. Window lengths are tuned online as a function of the estimated variation, while Whittle indices are computed via an upper-confidence-bound of the estimated transition kernels and a bilinear optimization routine. Numerical experiments demonstrate that our algorithm consistently outperforms baselines, achieving the lowest cumulative regret across a range of non-stationary environments.

Related papers

• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  This paper revisits the weighted strategy for non-stationary parametric bandits.<n>We propose a simpler weight-based algorithm that is as efficient as window/restart-based algorithms.<n>Our framework can be used to improve regret bounds of other parametric bandits.
  arXiv  Detail & Related papers  (2026-01-03T04:50:21Z)
• Non-stationary Bandit Convex Optimization: A Comprehensive Study [28.086802754034828]
  Bandit Convex Optimization is a class of sequential decision-making problems.<n>We study this problem in non-stationary environments.<n>We aim to minimize the regret under three standard measures of non-stationarity.
  arXiv  Detail & Related papers  (2025-06-03T15:18:41Z)
• Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration [6.287267171078442]
  We propose variance-aware algorithms that leverage neural networks to approximate nonlinear utility functions.<n>We establish theoretical guarantees showing that our algorithms achieve sublinear cumulative average regret of order $bigollt(d sqrtsum_t=1T sigma_t2 + sqrtdTrt),$ for sufficiently wide neural networks.
  arXiv  Detail & Related papers  (2025-06-02T01:58:48Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• Near-Optimal Algorithm for Non-Stationary Kernelized Bandits [6.379833644595456]
  We study a non-stationary kernelized bandit (KB) problem, also called time-varying Bayesian optimization. We show the first algorithm-independent regret lower bound for non-stationary KB with squared exponential and Mat'ern kernels. We propose a novel near-optimal algorithm called restarting phased elimination with random permutation.
  arXiv  Detail & Related papers  (2024-10-21T14:28:26Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  An ideal set of kernels should: admit a linear parameterization (for tractability); dense in the set of all kernels (for accuracy) Previous algorithms for optimization of kernels were limited to classification and relied on computationally complex Semidefinite Programming (SDP) algorithms. We propose a SVD-QCQPQP algorithm which dramatically reduces the computational complexity as compared with previous SDP-based approaches.
  arXiv  Detail & Related papers  (2023-04-15T04:57:37Z)
• Provably Efficient Model-Free Algorithms for Non-stationary CMDPs [10.930095238723327]
  We study model-free reinforcement learning algorithms in episodic non-stationary constrained Markov Decision Processes. In the non-stationary environment, reward, utility functions, and transition kernels can vary arbitrarily over time as long as the cumulative variations do not exceed certain variation budgets. We propose the first model-free, simulator-free RL algorithms with sublinear regret and zero constraint violation for non-stationary CMDPs.
  arXiv  Detail & Related papers  (2023-03-10T06:33:38Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.<n>An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge [23.890686553141798]
  We propose an algorithm for non-stationary kernel bandits that does not require prior knowledge of the degree of non-stationarity. Our algorithm enjoys a tighter dynamic regret bound than previous work on the non-stationary kernel bandit setting.
  arXiv  Detail & Related papers  (2022-05-29T21:32:53Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  The area under the ROC curve (AUC) is one of the most widely used performance measures for classification models in machine learning. We develop an efficient approximated gradient descent method based on recent practical envelope smoothing technique. Our proposed algorithm can also be used to minimize the sum of some ranked range loss, which also lacks efficient solvers.
  arXiv  Detail & Related papers  (2022-03-03T03:46:18Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Cost Function Unrolling in Unsupervised Optical Flow [6.656273171776146]
  This work focuses on the derivation of the Total Variation semi-norm commonly used in unsupervised cost functions. We derive a differentiable proxy to the hard L1 smoothness constraint in a novel iterative scheme which we refer to as Cost Unrolling.
  arXiv  Detail & Related papers  (2020-11-30T14:10:03Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  We investigate online convex optimization in non-stationary environments. We choose the dynamic regret as the performance measure. We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
  arXiv  Detail & Related papers  (2020-07-07T14:10:57Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Taming neural networks with TUSLA: Non-convex learning via adaptive stochastic gradient Langevin algorithms [0.0]
  We offer on an appropriately constructed gradient algorithm based on problematic Lange dynamics (SGLD) We also provide nonasymptotic analysis of the use of new algorithm's convergence properties. The roots of the TUSLA algorithm are based on the taming processes with developed coefficients citettamed-euler.
  arXiv  Detail & Related papers  (2020-06-25T16:06:22Z)
• Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting [31.60239268539764]
  PFSGD algorithms do not require setting learning rates while achieving optimal theoretical performance. In this paper, we close the empirical gap with a new parameter-free algorithm based on continuous-time Coin-Betting on truncated models. We show empirically that this new parameter-free algorithm outperforms algorithms with the "best default" learning rates and almost matches the performance of finely tuned baselines without anything to tune.
  arXiv  Detail & Related papers  (2020-06-12T23:10:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.