Restless Bandits with Individual Penalty Constraints: A New Near-Optimal Index Policy and How to Learn It

• URL: http://arxiv.org/abs/2604.04101v1
• Date: Sun, 05 Apr 2026 12:53:10 GMT
• Title: Restless Bandits with Individual Penalty Constraints: A New Near-Optimal Index Policy and How to Learn It
• Abstract summary: This paper investigates the Restless Multi-Armed Bandit (RMAB) framework under individual penalty constraints to address resource allocation challenges in wireless networked environments.<n>Unlike conventional RMAB models, our model allows each user (arm) to have distinct and stringent performance constraints, such as energy limits, activation limits, or age of information minimums.<n>To find the optimal resource allocation policy, we propose a new Penalty- Optimal Whittle (POW) index policy.
• Score: 8.559763606620937
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the Restless Multi-Armed Bandit (RMAB) framework under individual penalty constraints to address resource allocation challenges in dynamic wireless networked environments. Unlike conventional RMAB models, our model allows each user (arm) to have distinct and stringent performance constraints, such as energy limits, activation limits, or age of information minimums, enabling the capture of diverse objectives including fairness and efficiency. To find the optimal resource allocation policy, we propose a new Penalty-Optimal Whittle (POW) index policy. The POW index of an user only depends on the user's transition kernel and penalty constraints, and remains invariable to system-wide features such as the number of users present and the amount of resource available. This makes it computationally tractable to calculate the POW Indices offline without any need for online adaptation. Moreover, we theoretically prove that the POW index policy is asymptotically optimal while satisfying all individual penalty constraints. We also introduce a deep reinforcement learning algorithm to efficiently learn the POW index on the fly. Simulation results across various applications and system configurations further demonstrate that the POW index policy not only has near-optimal performance but also significantly outperforms other existing policies.

Related papers

• OGPO: Sample Efficient Full-Finetuning of Generative Control Policies [53.42266064673132]
  Generative control policies (GCPs) have emerged as effective parameterizations for robot learning.<n>This work introduces Off-policy Generative Policy Optimization (OGPO), a sample-efficient for finetuning GCPs.<n>OGPO achieves state-of-the-art performance on manipulation tasks spanning multi-task settings, high-precision insertion, and dexterous control.
  arXiv  Detail & Related papers  (2026-05-04T18:36:40Z)
• PolicyFlow: Policy Optimization with Continuous Normalizing Flow in Reinforcement Learning [6.836651088754774]
  PolicyFlow is a novel on-policy CNF-based reinforcement learning algorithm.<n>It integrates expressive CNF policies with PPO-style objectives without requiring likelihood evaluation along the full flow path.<n>PolicyFlow approximates importance ratios using velocity field variations along a simple path, reducing computational overhead without compromising training stability.
  arXiv  Detail & Related papers  (2026-02-01T11:08:09Z)
• Coverage Improvement and Fast Convergence of On-policy Preference Learning [67.36750525893514]
  Online on-policy preference learning algorithms for language model alignment can significantly outperform their offline counterparts.<n>We analyze how the sampling policy's coverage evolves throughout on-policy training.<n>We develop principled on-policy schemes for reward distillation in the general function class setting.
  arXiv  Detail & Related papers  (2026-01-13T10:46:06Z)
• Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
  offline reinforcement learning (RL) algorithms typically impose constraints on action selection.<n>We propose a new neighborhood constraint that restricts action selection in the Bellman target to the union of neighborhoods of dataset actions.<n>We develop a simple yet effective algorithm, Adaptive Neighborhood-constrained Q learning (ANQ), to perform Q learning with target actions satisfying this constraint.
  arXiv  Detail & Related papers  (2025-11-04T13:42:05Z)
• Deep Index Policy for Multi-Resource Restless Matching Bandit and Its Application in Multi-Channel Scheduling [6.648181286553698]
  We discuss a multi-resource restless matching bandit (MR-RMB) model for heterogeneous resource systems. We introduce a new Deep Index Policy (DIP), an online learning algorithm tailored for MR-RMB. Our simulation results show that DIP indeed learns the partial indexes efficiently.
  arXiv  Detail & Related papers  (2024-08-13T21:24:14Z)
• Hundreds Guide Millions: Adaptive Offline Reinforcement Learning with Expert Guidance [74.31779732754697]
  We propose a novel plug-in approach named Guided Offline RL (GORL) GORL employs a guiding network, along with only a few expert demonstrations, to adaptively determine the relative importance of the policy improvement and policy constraint for every sample. Experiments on various environments suggest that GORL can be easily installed on most offline RL algorithms with statistically significant performance improvements.
  arXiv  Detail & Related papers  (2023-09-04T08:59:04Z)
• Deep Reinforcement Learning for Inventory Networks: Toward Reliable Policy Optimization [2.9016349714298157]
  We argue that inventory management presents unique opportunities for the reliable application of deep reinforcement learning (DRL)<n>The first is Hindsight Differentiable Policy Optimization (HDPO), which uses pathwise gradients from offline counterfactual simulations to directly and efficiently optimize policy performance.<n>We exploit Graph Neural Networks (GNNs) as a natural inductive bias for encoding supply chain structure, demonstrate that they can represent optimal and near-optimal policies in two theoretical settings, and empirically show that they reduce data requirements across six diverse inventory problems.
  arXiv  Detail & Related papers  (2023-06-20T02:58:25Z)
• Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits [30.532795983761314]
  We study the problem of planning restless multi-armed bandits (RMABs) with multiple actions. We first show that Whittle index policies can fail in simple and practically relevant settings. We then propose an alternate planning algorithm based on the mean-field method.
  arXiv  Detail & Related papers  (2022-10-31T19:35:15Z)
• Learning Resilient Radio Resource Management Policies with Graph Neural Networks [124.89036526192268]
  We formulate a resilient radio resource management problem with per-user minimum-capacity constraints. We show that we can parameterize the user selection and power control policies using a finite set of parameters. Thanks to such adaptation, our proposed method achieves a superior tradeoff between the average rate and the 5th percentile rate.
  arXiv  Detail & Related papers  (2022-03-07T19:40:39Z)
• DNN-based Policies for Stochastic AC OPF [7.551130027327462]
  optimal power flow (SOPF) formulations provide a mechanism to handle uncertainties by computing dispatch decisions and control policies that maintain feasibility under uncertainty. We put forth a deep neural network (DNN)-based policy that predicts the generator dispatch decisions in response to uncertainty. The advantages of the DNN policy over simpler policies and their efficacy in enforcing safety limits and producing near optimal solutions are demonstrated.
  arXiv  Detail & Related papers  (2021-12-04T22:26:27Z)
• Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks [59.419152768018506]
  We show that any optimal policy necessarily satisfies the k-SP constraint. We propose a novel cost function that penalizes the policy violating SP constraint, instead of completely excluding it. Our experiments on MiniGrid, DeepMind Lab, Atari, and Fetch show that the proposed method significantly improves proximal policy optimization (PPO)
  arXiv  Detail & Related papers  (2021-07-13T21:39:21Z)
• Iterative Amortized Policy Optimization [147.63129234446197]
  Policy networks are a central feature of deep reinforcement learning (RL) algorithms for continuous control. From the variational inference perspective, policy networks are a form of textitamortized optimization, optimizing network parameters rather than the policy distributions directly. We demonstrate that iterative amortized policy optimization, yields performance improvements over direct amortization on benchmark continuous control tasks.
  arXiv  Detail & Related papers  (2020-10-20T23:25:42Z)

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.