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.
Figures & tables
Figure 1. Average reward and average constraint violation for throughput maximization with activation constraints.
Figure 2. Comparison of learning policies for throughput maximization with activation constraints.
Figure 3. Average reward and average constraint violation for remote sensing.
Figure 4. Comparison of learning policies for remote sensing.
Figure 5. Average reward and average constraint violation for throughput maximization with service regularity.
Figure 6. Comparison of learning policies for throughput maximization with service regularity.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
TP w/ Activation Constraint
(N,C)
θ0
θ1
δ
(4,1)
[.3,.5,.7,.9]
4×[.02]
[.35,.35,.05,.05]
(6,1)
[.3,.4,…,.9]
6×[.02]
[.2,.2,.1,.1,.05,.05]
Remote Sensing
(N,C)
p
B
(4,1)
[.2,.4,.6,.8]
[.9,.9,.1,.1]
Appendix
Table 1. Parameter settings for all three simulation scenarios.
We study a restless multi-armed bandit (RMAB) problem for a stochastic deadline scheduling application. RMAB problems are solved using the Whittle index policy. The goal in RMAB is to maximize the expected cumulative discounted reward maximization. The Whittle index policy maximizes reward, but is not fair among two classes. In this paper, we introduce fairness criteria and study an outcome-fair model for RMAB which allows fairness for jobs and users structurally disadvantaged demographic classes. We formulate an outcome fair stochastic deadline scheduling problem as RMAB, and we develop the outcome fair Whittle index policy. We define a virtual queue mechanism that dynamically enforces long-term completion rate guaranties across demographic groups. We analyze a standard Whittle index policy and the outcome-fair index policy. We demonstrate the performance of our algorithms with numerical examples. We compare policies---Whittle index policy (no fairness), input-fairness Whittle index policy, outcome fair Whittle index policy. We observe that the outcome-fair Whittle index policy provides better fairness among classes compared to other policies. We demonstrate a trade off between fairness and profit. This decreases as the server capacity increases.
Shakti Sharma, Rahul Meshram
Dept. of Physics, IIT Madras, Chennai, India. · Dept. of Electrical Engineering, IIT Madras, Chennai, India.
We study restless bandits with binary latent states and imperfect binary feedback, motivated by opportunistic spectrum access with sensing errors. For the associated belief-state model, we develop a partial conservation laws (PCL)-based analytical and computational framework for establishing indexability and evaluating the Whittle index, building on a verification theorem for real-state discounted restless bandits. The framework analyzes the stochastic dynamics via an associated deterministic skeleton, renewal decompositions, and combinatorics on words. It yields tractable expressions for discounted reward and resource metrics in several threshold regimes, enabling full verification of the PCL-indexability conditions there. For the remaining regime, where a complete analytic verification is not achieved in this paper, we derive efficient numerical schemes for computing the relevant marginal metrics and the marginal productivity (MP) index, which equals the Whittle index when those conditions hold. Extensive computational experiments provide strong evidence that these conditions also hold in that regime across broad parameter ranges and without the stringent parameter restrictions imposed in prior work. The experiments further show that theMP index policy typically outperforms standard benchmark policies, often by a substantial margin.
José Niño-Mora
Departamento de Estadística Universidad Carlos III de Madrid 28903 Getafe (Madrid), Spain
Many decision-making problems in computing and networking systems can be naturally formulated as cost-minimization problems under performance constraints. In dynamic environments, reinforcement learning (RL) is often used to solve such problems at runtime by embedding both costs and constraint violations into a single scalar reward through weighted penalty terms, following a Lagrangian-inspired formulation. However, in this context the behavior of the learned policy critically depends on the choice of these weights, which are typically selected manually. This makes it difficult to identify an appropriate trade-off between optimizing the primary objective and effectively avoiding constraint violations, particularly in non-stationary environments where their relative importance may change. This paper presents MAMO (Multi-Agent system for Multi-Objective constrained optimization), an approach to tackle this balancing problem through multi-agent RL. MAMO decouples task execution from objective design by formulating the selection of reward weights as a learning problem, providing a !rst step towards more autonomous and robust RL-based solutions for constrained optimization problems in dynamic environments.