acceptodds
Under review as a conference paper at ICLR 2027

Swiftly Generating Whittle Index in a Changing Environment: An Environment Parameter-Driven Actor-Critic Approach

Abstract

Whittle index provides a low-complexity and adaptive solution to large-scale restless multi-armed bandit (RMAB) problems. However, in practice, when the environment faced by each arm constantly changes, the Whittle index has to be repeatedly recomputed, which incurs exceedingly high computational complexity. In this paper, we develop a new environment parameter-driven neural-network approach for generating the Whittle index for constantly-changing environments. Our neural network only needs to be trained once, and it can instantly produce the Whittle index for a new environment in real-time, as soon as the new environment can be identified by its environment parameter (which can be estimated by either a hand-crafted estimator or a trained environment encoder). We further provide a new Whittle Actor-Critic (WAC) pipeline to train the index network. Compared to the prior Whittle Q-Learning pipeline, our new WAC pipeline is less sensitive to the neural-network size and can produce meaningful index-like policies even for non-indexable problems. Numerical results show that our WAC outperforms other baselines in a broad range of RMAB settings in terms of both index accuracy and control performance.

Primary area:
reinforcement learning
Keywords:
Restless multi-armed bandits, Whittle index, non-stationary environments, actor-critic, reinforcement learning, environment-conditioned neural networks

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_URpXOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper aims to build RL algorithms to learn the Whittle index in constantly changing environments. The main idea is to employ domain randomization to expand existing Whittle-index-learning algorithms, mostly DeepTOP (Nakhleh et al., 2022). The main idea is to treat the estimated environmental parameters as part of the inputs to the actor neural network. The paper conducts experiments on a environment that can be characterized by only two parameters and show that their algorithm adapts well in such environments.

Critical strengths
  1. The paper has a clear use case as its target application (wireless scheduling) indeed suffers from frequent environmental changes.
  2. Simulation results show that its algorithm is better than DeepTOP.
Critical weaknesses
  1. The novelty of the paper appears to be insufficient. Using domain randomization to learn a policy that can operate in a range of environments is a commonly-used technique. The paper seems to be a straightforward application of domain randomization on DeepTOP. Since domain randomization can be applied to virtually any RL algorithms, it is not surprising that it can be applied to DeepTOP.

  2. The simulations are limited to very simple environments that can be characterized by only two parameters. There is little doubt that naive domain randomization can easily handle such simple environments.

  3. The paper seems to suggest that the derivation from Eq. (6) to Eq. (7) is an important difficulty that separates this paper from DeepTOP. The claim is that Eq. (6) involves the initial state distribution \mu while Eq. (7) involves the specific state s_j, and the paper claims the latter is better for learning. However, it is not clear if this is indeed a new contribution of this paper. Looking at Eq. (3) from DeepTOP, the equation appears to be in the form of Eq. (7), rather than Eq. (6), since it is the state v that is inside the Q function.

Questions for authors

None.

5 comments
AuthorsOpenReview ↗

Response to Weakness 1 (Part 1)

(W1: The novelty of WAC, Part 1/2) We respectfully disagree that our method is a minor extension of DeepTOP. First, we wish to bring to the reviewer's attention that, although DeepTOP reported a similar objective function as our WAC (and inspired our pipeline), it is NOT an actor-critic algorithm because it does NOT optimize this objective. To see this, we first reproduce below the gradient of the training objective and the main equation from DeepTOP. Their derived gradient of the training objective K(μϕ)K(\mu^{\phi}) is the following (see Eq. (11) of DeepTOP).

\nabla_{\phi} K(\mu^{\phi}) = |\mathcal{S}| \sum_{s\in\mathcal{S}} \bar{\rho}_{\mu^{\phi}(s)}(s) \bigl(Q_{\mu^{\phi}(s)}(s,1) - Q_{\mu^{\phi}(s)}(s,0)\bigr) \nabla_{\phi}\mu^{\phi}(s). \tag{i}

On the other hand, when they train the Q-function values, they use the difference of the Bellman equation (the following is Eq. (12) of their paper):

\mathcal{L}(\theta) := \int_{\lambda=-M}^{\lambda=+M} \mathbb{E}_{s_t,a_t,r_t,s_{t+1}} \left[\left( Q_{\lambda}^{\theta}(s_t,a_t) -r_t -\gamma\max_{a'\in\mathcal{A}}Q_{\lambda}^{\theta'}(s_{t+1},a') \right)^2\right] \mathrm{d}\lambda. \tag{ii}

Here, θ\theta is the Q-network parameters; the latter θ′\theta' is updated by an exponential moving average of θ\theta. [1]

[1] Also, in the released code at https://github.com/khalednakhleh/deeptop, the critic is updated by optimal Q-learning with a greedy target: in RMAB/DeepTOP.py, update_policy(), the next action is chosen as arg⁡max⁡aQ(s′,a)\arg\max_a Q(s',a) (line 101).

However, the confusion arises because, even though the two Qλ(s,a)Q_{\lambda}(s,a) share the same notation, they stand for very different meanings. The Qμϕ(s,a)Q_{\mu^{\phi}}(s,a) in Eq. (i) represents the Q-function with respect to the current threshold policy based on the index values μϕ(s)\mu^{\phi}(s). Indeed, it is defined in Eq. (9) of DeepTOP:

Q_{\lambda}\bigl(s,\mathbf{1}(\mu(s) > \lambda)\bigr)=\sum_{s'\in\mathcal{S}}\rho_{\mu,\lambda}(s',s) \left(\bar{r}\bigl(s',\mathbf{1}(\mu(s') > \lambda)\bigr) -\lambda\mathbf{1}(\mu(s') > \lambda)\right). \tag{iii}

From here, we can see that, every time state s′s' is reached, the corresponding action is supposed to be determined by 1μϕ(s′)>λ1_{\mu^{\phi}(s') > \lambda}, which is exactly the threshold policy based on the current index values μϕ(s′)\mu^{\phi}(s'). In contrast, Qλθ(s,a)Q_{\lambda}^{\theta}(s,a) used in Eq. (ii) is the Q-function of the optimal policy since in Eq. (ii) there is a max⁡\max operator. Since these two Q-functions are different, substituting the Qλθ(st,at)Q_{\lambda}^{\theta}(s_t,a_t) learned from Eq. (ii) into Eq. (i) does NOT optimize the original actor-critic objective K(μϕ)K(\mu^{\phi}). Therefore, we can conclude that, even though DeepTOP reported a similar objective function, the training method Eq. (ii) that they provided does NOT really optimize this objective.

(Continued in the next reply.)

AuthorsOpenReview ↗

Response to Weakness 1 (Part 2)

(W1: The novelty of WAC, Part 2/2)

Let us denote Qλ∗(s,a)Q^{\ast}_{\lambda}(s,a) as the optimal Q-function learned from Eq. (ii), to differentiate from the Q-function based on the current threshold policy. If we were to substitute the notation Qλ∗(s,a)Q^{\ast}_{\lambda}(s,a) into Eq. (i), then using mini-batch estimation, the actual gradient of DeepTOP would have become:

\widehat{\nabla}_{\phi} K(\mu^{\phi}) := \frac{1}{B}\sum_{k=1}^{B} \bigl(Q_{\mu^{\phi}(s_{t_k})}^{\ast}(s_{t_k},1) - Q_{\mu^{\phi}(s_{t_k})}^{\ast}(s_{t_k},0)\bigr) \nabla_{\phi}\mu^{\phi}(s_{t_k}). \tag{iv}

As shown in Eq. (9) in Appendix A of our paper, this is exactly the gradient of Whittle Q-learning algorithm. Therefore, we argue that DeepTOP trained by Eq. (ii) is not a Whittle Actor-Critic (WAC) algorithm but instead a Whittle Q-learning (WQL) algorithm. To the best of our knowledge, our WAC is the first Actor-Critic algorithm in the literature for index learning.

Table I. Final index error of WAC improve significantly with the two introduced techniques.

MethodFinal index error
Using Original gradient, Eq. (6)0.5403
Using Modified gradient, Eq. (7)0.2384
Using Modified and rollout0.0884

Second, since DeepTOP is not really an actor-critic method, it does not address the unique challenges of Whittle Actor-Critic methods. As we have explained in the paper, in order to implement WAC in an effective way, there are many challenges to overcome. Thus, our contribution is in addressing these challenges. The first challenge is that the objective's original gradient is often close to zero and thus hard to optimize. We introduce a modified gradient with a different initial state (Section 3.1) to stabilize training. The second challenge is that the policy-dependent value function (corresponding to the policy-dependent Qλ(s,a)Q_{\lambda}(s,a) in Eq. (i)) is difficult to train using Temporal Difference alone. We introduce a rollout mechanism to improve the estimation of the value function. Here, we also report the final index error of WAC with and without these techniques in Table I. As shown in Table I, the modified gradient reduces the final index error to 4444\\% compared to the original gradient. With an additional rollout, it further reduces to only 1616 \\% of using the original gradient (also see the newly-added Figure 7 of our revised paper).

Finally, we also explore the theoretical properties of WAC. We prove that, under reasonable assumptions, the WAC training objective has no stationary point other than the Whittle index. As discussed in Appendix F, such a result is non-trivial. We also discover that WAC has an advantage when the problem is non-indexable, and demonstrate this through both theoretical analysis and experiments.

In conclusion, our algorithm should not be viewed as an extension of DeepTOP. DeepTOP is not an Actor-Critic algorithm and does not address the unique issues related to Actor-Critic. Our algorithm is the first one that actually applies the Actor-Critic method to index learning. Our WAC algorithm not only learns the index values correctly, but also outperforms Whittle Q-Learning in terms of the index error and RMAB control performance. Therefore, we believe that these represent significant contributions.

AuthorsOpenReview ↗

Response to Weakness 2 and 3

(W2: More environment parameter experiments) Our WAC method is not restricted to two environment parameters: it is effective even when we consider environments with multiple environment parameters. Below, we extend our experiments to environments that have 66 and 1010 parameters, where we fix the environment encoder's output dimension to be 55. The results reported in the following table show that our methods can generalize to environments with more parameters. These multi-parameter environments are constructed based on the 2D maintenance environment. Our method still outperforms WQL in these multi-parameter environments.

MethodsWACWQLDeepTOPRandom
6 parameters env657.84 ± 5.69666.28 ± 4.38794.83 ± 5.02953.46 ± 1.57
10 parameters env508.58 ± 7.05538.92 ± 10.15620.40 ± 4.93764.30 ± 4.67

(W3: Distinction of our modified gradient Eq. (7) in our paper and Eq. (3) in DeepTOP) We wish to clarify that Eq. (3) in DeepTOP still assumes uniform initial states. Specifically, although ν\nu in Eq. (3) of DeepTOP is similar to sjs_j in Eq. (6) of our paper, it only means that the two policies being evaluated differed at state ν\nu (or sjs_j). The initial state distribution is still uniform, and thus Eq. (3) is not the same as Eq. (7) in our paper, which uses sjs_j as the initial state.

To see this, we reproduce Eq. (3) of DeepTOP below:

\nabla_{\phi} K(\mu^{\phi}) =|\mathcal{S}| \sum_{\nu \in\mathcal{S}} \bar{\rho}_{\mu^{\phi}(\nu)}(\nu) \bigl(Q_{\mu^{\phi}(\nu)}(\nu,1) - Q_{\mu^{\phi}(\nu)}(\nu,0)\bigr) \nabla_{\phi}\mu^{\phi}(\nu). \tag{v}

In the first equation on page 15 of our paper, we show that

V^{P \setminus \\{s_j\\}}(\mu,\lambda) - V^{P}(\mu,\lambda) = \rho_{\mu}^{P \setminus \\{s_j\\}}(s_j)\left(Q^{P}_{\lambda}(s_j,1) - Q^{P}_{\lambda}(s_j,0)\right), \tag{vi}

where sjs_j represents a state and μ\mu is the initial distribution. Note that the RHS of Eq. (v) is similar to the RHS of Eq. (vi), with ν\nu replaced by sjs_j.

To understand Eq. (vi), consider two policies that differ at state sjs_j. Regardless of the initial state distribution μ\mu, the difference of value function (left hand side of Eq. (vi)) can be written as the “visitation measure ρμ\rho_{\mu}” multiplied by the Q-function difference at state sjs_j. Hence, it is clear that both ν\nu of Eq. (v) and sjs_j of Eq. (vi) inside the Q function correspond to two policies taking different actions at state ν\nu (or sjs_j). Note that this is independent of the initial time distribution μ\mu.

Therefore, we can see that Eq. (3) of DeepTOP is equivalent with our Eq. (6), which is copied below for the convenience of the reviewer,

\Bigl( V_{{{\lambda_j(z)}}}^{P \setminus \\{s_j\\}}(\mu,z) -V_{{{\lambda_j(z)}}}^{P}(\mu,z) \Bigr) \nabla_{\theta} \phi_{\theta}(s_j,z), \tag{vii}

The initial distribution μ\mu here ( and in Eq. (6) of our paper) is chosen as the uniform distribution. Similarly, above Eq. (3) of DeepTOP, the paper states that “the initial state is chosen uniformly at random”. Hence, they both use the uniform distribution as the initial distribution, and by the above Eq. (vi), are the same.

Finally, we can see that both of them are very different from Eq. (7) of our paper, which is copied below for the convenience of the reviewer:

\Bigl( V_{{{\lambda_j(z)}}}^{P \setminus \\{s_j\\}}(s_j,z) -V_{{{\lambda_j(z)}}}^{P}(s_j,z) \Bigr) \nabla_{\theta} \phi_{\theta}(s_j,z) \tag{viii}

The initial distribution μ\mu in Eq. (vii) is replaced by sjs_j inside the value function in Eq. (viii) . This means that the value functions in Eq. (viii) ( and Eq. (7) of our paper) will be evaluated with an initial state being exactly sjs_j, instead of the uniform μ\mu. This modification is important for training: without this modification, the original gradient is too small and training is unstable.

In summary, even though ν\nu in Eq. (3) of DeepTOP appears to play a similar role as sjs_j in Eq. (7) in our paper, Eq. (3) of DeepTOP still assumes uniform initial states, and is therefore very different from Eq. (7) in our paper. Using this new initial state distribution is also a main contribution of our paper.

Reviewer_TqUKOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper trains a network to predict approximate Whittle index from environment parameters. Once trained, it can update these predictions as the environment changes, avoiding repeated training from scratch. The proposed WAC procedure evaluates the current threshold policies and uses rollouts to improve the value estimates. It also learns ranking policies for non-indexable problems, where Whittle indices are not defined. The experiments show that WAC outperforms WQL on the tested tasks, particularly with small networks and in the non-indexable setting. However, in the reported ablation, WAC without rollout performs similarly to WQL.

Critical strengths

S1: This paper feeds environmental parameters or learned environment representations into an index network. After a single offline training run, the model can generate an approximate Whittle index by forward inference when given a new environment representation.

S2: Experiments show that WAC is more robust than WQL to limited model capacity and achieves lower index error and control cost across the model sizes examined.

S3: The authors analyze the gradient and optimization properties of the index-learning objective. This helps clarify the method’s theoretical basis, and the detailed appendix makes the assumptions and derivations easier to verify.

Critical weaknesses

W1: The actor–critic framework alone is not enough to establish novelty. Existing work already uses a shared actor–critic based on arm features to generalize across arms; DeepTOP has already studied learning Whittle indices through threshold policies; and Appendix C of this paper shows that, in a fixed environment, the two objective functions differ only by a constant factor. The paper does differ in index output, policy value estimation, and training implementation, but the current discussion does not make clear how far these changes amount to an independent methodological contribution.

W2: Under the setup in Appendix M, Table 3a, WAC without rollout has index error (0.40±0.19), close to the WQL mean of (0.42±0.02); with one-step rollout, the error falls to (0.17±0.01). The configuration labeled as using no critic also reaches (0.17±0.04). These results suggest that the marked improvement in this setting is closely tied to rollout, and they do not yet show that the learned critic is the key to the performance gain.

W3: Eq. (53) in Appendix I holds only for nonnegative Lagrange multipliers, but Eq. (54) directly substitutes the lowest activated index λ ̂, and the paper does not guarantee that this index is nonnegative. When the original problem allows the budget not to be fully used while the index policy always activates exactly the budgeted number of arms, one can construct a counterexample that satisfies the stated assumptions but violates Theorem I.2.

Questions for authors

Q1: How much extra computation and interaction cost does the accuracy gain from rollout entail?

Q2: How does Theorem I.2 handle the case where the lowest activated index is negative?

Q3: Does Table 3 really show that the actor–critic mechanism drives the gain?

8 comments
AuthorsOpenReview ↗

Response to Question 1 and Question 2 (part 1)

(Q1: extra computation and interaction cost in rollout) In our experiments, we have been careful to ensure that WAC uses no extra simulation cost nor extra computation cost involving rollout. Specifically, in table 3, whenever we increase the rollout horizon TT, we decrease the number of value-function updates JJ, to keep the total simulation count the same (T+J=20T+J=20). In comparison, our experiment with the Q-learning method also utilizes 20 Q-function updates, each update drawing new samples. Thus, in all these experiments, the interaction cost of WAC and WQL are kept the same (we don't use any buffer for WQL since we find that using buffer for index learning is not stable. One possible reason is that for index learning, we need to learn an accurate optimal Q-value for both actions, but imbalanced sampling from the replay buffer may impair Q-value estimation).

Moreover, even with the same number of samples, WAC with rollout even incurs lower computational cost than WQL. This is because WAC allocates a portion of its samples to rollout, which is cheaper compared with using all samples for updating the value-network. The former requires one forward pass of the value-function network, without any need for backward propagation. Please see Figure 8 of our newly uploaded pdf, which shows the index error against the estimated training flops for the rollout ablations in Table 3. Notably, the WAC with the most rollout has the least training computation flops.

(Q2: Negative index case of Theorem 4.2, Part 1/2) We thank the reviewer for pointing out this important gap. We acknowledge that the current proof only works when all indices are non-negative. However, it is not hard to revise our method to accommodate the case when some indices are negative. Recall that the learned index at ss is ϕθ(s)\phi_{\theta}(s). Specifically, we can replace our index policy by one that uses a max-weight formulation:

\begin{aligned} \max_{\\{u_i\\}} \quad & \sum_{i=1}^{N} \phi_{\theta}(s_i) u_i \\\\ \text{s.t.} \quad & \sum_{i=1}^{N} u_i \le C, \\\\ & u_i \in \\{0,1\\}, \quad \forall i. \end{aligned} \tag{i}

Here sis_i is the state of arm ii and uiu_i is the decision for whether activating it or not. It is easy to see that this policy is equivalent to "scheduling the highest non-negative indices within the capacity constraints". Note that if all the arms with non-negative indices have been scheduled, yet the capacity budget CC has not been reached, this policy will stop and will not schedule the agents with negative indices.

We now discuss how to fix the proof after we adopt the above policy. We will repair our proof from Eq. (52) to Eq. (55) in the paper. The arguments before Eq. (52) and after Eq. (55) remain the same and thus we will assume that a global attractor x∗x^{\ast} has been reached under the above index policy.

At the global attractor x∗x^{\ast}, the corresponding max-weight decision Eq. (i) can be equivalently written as follows:

\begin{aligned} \max_{u}\quad& \sum_s \phi_\theta(s)u(s;x^{\ast})\\\\ \text{s.t.}\quad& \sum_s u(s;x^{\ast})\le\rho,\\\\ &0\le u(s;x^{\ast})\le x^{\ast}(s),\quad \forall s. \end{aligned} \tag{ii}

Here u(s;x∗)u(s;x^{\ast}) is the activation occupancy and the corresponding induced policy π^\widehat\pi is defined as

\widehat\pi(1\mid s) =\frac{u(s;x^{\ast})}{x^{\ast}(s)}, \qquad x^{\ast}(s) > 0. \tag{iii}

Define λ^\widehat\lambda as the optimal Lagrange multiplier associated with the capacity constraint of Eq. (ii). By the KKT conditions of Eq. (ii), we must have the following

\widehat\lambda\ge0,\qquad \widehat\lambda \left(\rho-\sum_su(s;x^{\ast})\right)=0. \tag{iv}

Second, the optimal allocation decision activate states with ϕθ(s)>λ^\phi_\theta(s) > \widehat\lambda, keeps states with ϕθ(s)<λ^\phi_\theta(s) < \widehat\lambda passive, and may randomize at states with ϕθ(s)=λ^\phi_\theta(s)=\widehat\lambda.

Note that the second part of Eq. (iv) now works even if the budget is not filled, i.e., ∑su(s,x∗)<ρ\sum_s u(s,x^{\ast}) < \rho. When that occurs, we will have λ^=0\widehat{\lambda}=0 (i.e., the complementary slackness condition).

(Continued in the next reply.)

AuthorsOpenReview ↗

Response to Question 2 (part 2) and Question 3

(Q2: Negative index case of Theorem 4.2, Part 2/2)

We now show how to use the above structure to prove Theorem 4.2 in the paper, which is copied below (slightly reworded for improved clarity): Theorem (Non-indexable average-cost guarantee).

Define Π~\tilde \Pi as the set of single-arm threshold policy satisfying the following properties: it will take active action when ϕθ(s)>λ^\phi_\theta(s) > \widehat \lambda, passive action when ϕθ(s)<λ^\phi_\theta(s) < \widehat \lambda, unspecified when ϕθ(s)=λ^\phi_\theta(s)=\widehat \lambda. If, for all π~∈Π~\tilde{\pi} \in \tilde{\Pi}, the following holds,

j^{\tilde \pi}(\widehat\lambda)+\widehat{\lambda} \alpha^{\tilde{\pi}}\le \inf_{\pi}(j^{\pi}(\widehat{\lambda})+\widehat{\lambda} \alpha^{\pi}) + \epsilon, \tag{v}

then the learned priority policy satisfies

\limsup_{N\to\infty}\bigl(J_N^\phi-J_N^{\mathrm{opt}}\bigr)\le\epsilon. \tag{vi}

For the proof, by the definition of the relaxed problem, for every η≥0\eta\ge0, we have

J_N^{\mathrm{opt}}\ge J_N^{\mathrm{rel}}\ge \inf_{\pi}(j^\pi(\eta)+\eta \alpha^{\pi}) - \eta\rho. \tag{vii}

Then, taking η=λ^\eta=\widehat\lambda (which is nonnegative by Eq. (iv)) and applying Eq. (vii), we first obtain

J_N^{\mathrm{opt}} \ge J_N^{\mathrm{rel}} \ge \inf_{\pi}(j^\pi(\widehat\lambda)+\widehat\lambda \alpha^{\pi}) -\widehat\lambda\rho \ge j^{\tilde\pi}(\widehat\lambda)+\widehat\lambda(\alpha^{\tilde\pi}-\rho)-\epsilon. \tag{viii}

where the last inequality follows from the assumed single-arm ϵ\epsilon-optimality.

Next, we note that the policy π^\widehat\pi induced by the fluid allocation has exactly the property of π~\tilde\pi. Combining this with Eq. (viii), we have:

J_N^{\mathrm{opt}} \ge J_N^{\mathrm{rel}} \ge j^{\widehat \pi}(\widehat\lambda)+\widehat\lambda(\alpha^{\widehat \pi}-\rho)-\epsilon. \tag{ix}

Furthermore, thanks to the complementary slackness Eq. (iv), we get λ^(απ^−ρ)=0\widehat\lambda(\alpha^{\widehat\pi}-\rho)=0. Thus, we have

j^{\widehat\pi}(\widehat\lambda) +\widehat\lambda(\alpha^{\widehat\pi}-\rho)-\epsilon = j^{\widehat\pi}(\widehat\lambda)-\epsilon. \tag{x}

Combining Eq. (ix) and Eq. (x), we obtain

J_N^{\mathrm{opt}}\ge j^{\widehat\pi}(\widehat\lambda)-\epsilon. \tag{xi}

The rest of the proof then follows the same line as the one after Eq. (55) in our paper.

(Q3: Importance of Actor-Critic Mechanism) The reviewer is correct that the gain comes directly from rollout. However, this gain from rollout is only possible because we are using an on-policy actor-critic method such as WAC. Therefore, the correct statement here is that this gain is due to the combination of WAC and rollout. To see this, note that rollout requires knowing the policy first, and then generate trajectories using this policy. In WAC, since we want to estimate the value function of the current threshold policy, we know exactly the policy. Thus, WAC can use rollout to boost the estimation accuracy. In contrast, in WQL, since it only estimates the optimal Q-function, the corresponding optimal policy is unknown during training. Thus, we cannot apply rollout to WQL. In summary, WAC and rollout combined together contribute to the improvement.

AuthorsOpenReview ↗

Response to Weakness 1 (Part 1)

(W1: The novelty of WAC, Part 1/2) We respectfully disagree that our method is a minor extension of DeepTOP. First, we wish to bring to the reviewer's attention that, although DeepTOP reported a similar objective function as our WAC (and inspired our pipeline), it is NOT an actor-critic algorithm because it does NOT optimize this objective. To see this, we first reproduce below the gradient of the training objective and the main equation from DeepTOP. Their derived gradient of the training objective K(μϕ)K(\mu^{\phi}) is the following (see Eq. (11) of DeepTOP).

\nabla_{\phi} K(\mu^{\phi}) = |\mathcal{S}| \sum_{s\in\mathcal{S}} \bar{\rho}_{\mu^{\phi}(s)}(s) \bigl(Q_{\mu^{\phi}(s)}(s,1) - Q_{\mu^{\phi}(s)}(s,0)\bigr) \nabla_{\phi}\mu^{\phi}(s). \tag{xii}

On the other hand, when they train the Q-function values, they use the difference of the Bellman equation (the following is Eq. (12) of their paper):

\mathcal{L}(\theta) := \int_{\lambda=-M}^{\lambda=+M} \mathbb{E}_{s_t,a_t,r_t,s_{t+1}} \left[\left( Q_{\lambda}^{\theta}(s_t,a_t) -r_t -\gamma\max_{a'\in\mathcal{A}}Q_{\lambda}^{\theta'}(s_{t+1},a') \right)^2\right] \mathrm{d}\lambda. \tag{xiii}

Here, θ\theta is the Q-network parameters; the latter θ′\theta' is updated by an exponential moving average of θ\theta. [1]

[1] In the released code at https://github.com/khalednakhleh/deeptop, the critic is updated by optimal Q-learning with a greedy target: in RMAB/DeepTOP.py, update_policy(), the next action is chosen as arg⁡max⁡aQ(s′,a)\arg\max_a Q(s',a) (line 101).

However, the confusion arises because, even though the two Qλ(s,a)Q_{\lambda}(s,a) share the same notation, they stand for very different meanings. The Qμϕ(s,a)Q_{\mu^{\phi}}(s,a) in Eq. (xii) represents the Q-function with respect to the current threshold policy based on the index values μϕ(s)\mu^{\phi}(s). Indeed, it is defined in Eq. (9) of DeepTOP:

Q_{\lambda}\bigl(s,\mathbf{1}(\mu(s) > \lambda)\bigr)=\sum_{s'\in\mathcal{S}}\rho_{\mu,\lambda}(s',s) \left(\bar{r}\bigl(s',\mathbf{1}(\mu(s') > \lambda)\bigr) -\lambda\mathbf{1}(\mu(s') > \lambda)\right). \tag{xiv}

From here, we can see that, every time state s′s' is reached, the corresponding action is supposed to be determined by 1μϕ(s′)>λ1_{\mu^{\phi}(s') > \lambda}, which is exactly the threshold policy based on the current index values μϕ(s′)\mu^{\phi}(s'). In contrast, Qλθ(s,a)Q_{\lambda}^{\theta}(s,a) used in Eq. (xiii) is the Q-function of the optimal policy since in Eq. (xiii) there is a max⁡\max operator. Since these two Q-functions are different, substituting the Qλθ(st,at)Q_{\lambda}^{\theta}(s_t,a_t) learned from Eq. (xiii) into Eq. (xii) does NOT optimize the original actor-critic objective K(μϕ)K(\mu^{\phi}). Therefore, we can conclude that, even though DeepTOP reported a similar objective function, the training method Eq. (xiii) that they provided does NOT really optimize this objective.

(Continued in the next reply.)

Reviewer_VYqeOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes an environment-conditioned Whittle actor-critic method for restless bandits. It evaluates current threshold policies using a critic and simulated rollouts, then learns indices that adapt to changing environment parameters. The analysis characterizes the policy objective under an active-time condition. Experiments test index accuracy, small networks, non-indexable arms, and adaptation in simulated environments.

Critical strengths
  1. Rollouts improve index estimation with small networks. Table 3 reports an error of 0.17 with one-step rollout, compared with 0.40 without rollout and 0.42 for WQL (page 35). This supports evaluating the current threshold policy rather than relying entirely on an estimate of the optimal value function.

  2. Theorem 4.1 explains when the tabular objective has no incorrect local minima. Appendices G and H prove the result and verify its active-time condition for several arm classes. The paper clearly distinguishes this result from a convergence guarantee for neural-network training (pages 7 and 20–29).

Critical weaknesses
  1. The non-indexable guarantee does not consistently handle the resource constraint. The original problem permits unused capacity, but Appendix I always fills the budget. The proof requires a nonnegative multiplier and then substitutes a learned cutoff without establishing its sign (page 31). If activity only adds cost, leaving every arm passive can be optimal, whereas filling the budget is worse. The theorem needs conditions that exclude this case or must explicitly require full budget use.

  2. The efficiency evidence is less complete than the index-accuracy evidence. Update counts and rollout ablations are provided, but simulator-transition counts, training time, and variation across runs for Table 2 are missing. The experiment settings also need clarification: Figure 2 uses 600 arms and 200 activations, while Appendix K.2 gives 200 arms and 30 activations with different parameter ranges (pages 8–9 and 34). These may be separate experiments, but their correspondence is unclear.

Questions for authors
  1. Does Theorem 4.2 require full budget use, or can capacity remain unused? How does the implemented policy handle negative indices, and what conditions justify the multiplier used in the proof?

  2. Which settings correspond to Figure 2 and Table 2? Can you report simulator-transition counts, training time, variation across runs, and the parameter distributions used for training and evaluation?

3 comments
AuthorsOpenReview ↗

Response to Q1 (part 1)

(Q1: Negative index case of Theorem 4.2, Part 1/2) We thank the reviewer for pointing out this important gap. We acknowledge that the current proof only works when all indices are non-negative. However, it is not hard to revise our method to accommodate the case when some indices are negative. Recall that the learned index at ss is ϕθ(s)\phi_{\theta}(s). Specifically, we can replace our index policy by one that uses a max-weight formulation:

\begin{aligned} \max_{\\{u_i\\}} \quad & \sum_{i=1}^{N} \phi_{\theta}(s_i) u_i \\\\ \text{s.t.} \quad & \sum_{i=1}^{N} u_i \le C, \\\\ & u_i \in \\{0,1\\}, \quad \forall i. \end{aligned} \tag{i}

Here sis_i is the state of arm ii and uiu_i is the decision for whether activating it or not. It is easy to see that this policy is equivalent to "scheduling the highest non-negative indices within the capacity constraints". Note that if all the arms with non-negative indices have been scheduled, yet the capacity budget CC has not been reached, this policy will stop and will not schedule the agents with negative indices.

We now discuss how to fix the proof after we adopt the above policy. We will repair our proof from Eq. (52) to Eq. (55) in the paper. The arguments before Eq. (52) and after Eq. (55) remain the same and thus we will assume that a global attractor x∗x^{\ast} has been reached under the above index policy.

At the global attractor x∗x^{\ast}, the corresponding max-weight decision Eq. (i) can be equivalently written as follows:

\begin{aligned} \max_{u}\quad& \sum_s \phi_\theta(s)u(s;x^{\ast})\\\\ \text{s.t.}\quad& \sum_s u(s;x^{\ast})\le\rho,\\\\ &0\le u(s;x^{\ast})\le x^{\ast}(s),\quad \forall s. \end{aligned} \tag{ii}

Here u(s;x∗)u(s;x^{\ast}) is the activation occupancy and the corresponding induced policy π^\widehat\pi is defined as

\widehat\pi(1\mid s) =\frac{u(s;x^{\ast})}{x^{\ast}(s)}, \qquad x^{\ast}(s) > 0. \tag{iii}

Define λ^\widehat\lambda as the optimal Lagrange multiplier associated with the capacity constraint of Eq. (ii). By the KKT conditions of Eq. (ii), we must have the following

\widehat\lambda\ge0,\qquad \widehat\lambda \left(\rho-\sum_su(s;x^{\ast})\right)=0. \tag{iv}

Second, the optimal allocation decision activate states with ϕθ(s)>λ^\phi_\theta(s) > \widehat\lambda, keeps states with ϕθ(s)<λ^\phi_\theta(s) < \widehat\lambda passive, and may randomize at states with ϕθ(s)=λ^\phi_\theta(s)=\widehat\lambda.

Note that the second part of Eq. (iv) now works even if the budget is not filled, i.e., ∑su(s,x∗)<ρ\sum_s u(s,x^{\ast}) < \rho. When that occurs, we will have λ^=0\widehat{\lambda}=0 (i.e., the complementary slackness condition).

(Continued in the next reply.)

AuthorsOpenReview ↗

Response to Q1 (part 2)

(Q1: Negative index case of Theorem 4.2, Part 2/2)

We now show how to use the above structure to prove Theorem 4.2 in the paper, which is copied below (slightly reworded for improved clarity): Theorem (Non-indexable average-cost guarantee).

Define Π~\tilde \Pi as the set of single-arm threshold policy satisfying the following properties: it will take active action when ϕθ(s)>λ^\phi_\theta(s) > \widehat \lambda, passive action when ϕθ(s)<λ^\phi_\theta(s) < \widehat \lambda, unspecified when ϕθ(s)=λ^\phi_\theta(s)=\widehat \lambda. If, for all π~∈Π~\tilde{\pi} \in \tilde{\Pi}, the following holds,

j^{\tilde \pi}(\widehat\lambda)+\widehat{\lambda} \alpha^{\tilde{\pi}}\le \inf_{\pi}(j^{\pi}(\widehat{\lambda})+\widehat{\lambda} \alpha^{\pi}) + \epsilon, \tag{v}

then the learned priority policy satisfies

\limsup_{N\to\infty}\bigl(J_N^\phi-J_N^{\mathrm{opt}}\bigr)\le\epsilon. \tag{vi}

For the proof, by the definition of the relaxed problem, for every η≥0\eta\ge0, we have

J_N^{\mathrm{opt}}\ge J_N^{\mathrm{rel}}\ge \inf_{\pi}(j^\pi(\eta)+\eta \alpha^{\pi}) - \eta\rho. \tag{vii}

Then, taking η=λ^\eta=\widehat\lambda (which is nonnegative by Eq. (iv)) and applying Eq. (vii), we first obtain

J_N^{\mathrm{opt}} \ge J_N^{\mathrm{rel}} \ge \inf_{\pi}(j^\pi(\widehat\lambda)+\widehat\lambda \alpha^{\pi}) -\widehat\lambda\rho \ge j^{\tilde\pi}(\widehat\lambda)+\widehat\lambda(\alpha^{\tilde\pi}-\rho)-\epsilon. \tag{viii}

where the last inequality follows from the assumed single-arm ϵ\epsilon-optimality.

Next, we note that the policy π^\widehat\pi induced by the fluid allocation has exactly the property of π~\tilde\pi. Combining this with Eq. (viii), we have:

J_N^{\mathrm{opt}} \ge J_N^{\mathrm{rel}} \ge j^{\widehat \pi}(\widehat\lambda)+\widehat\lambda(\alpha^{\widehat \pi}-\rho)-\epsilon. \tag{ix}

Furthermore, thanks to the complementary slackness Eq. (iv), we get λ^(απ^−ρ)=0\widehat\lambda(\alpha^{\widehat\pi}-\rho)=0. Thus, we have

j^{\widehat\pi}(\widehat\lambda) +\widehat\lambda(\alpha^{\widehat\pi}-\rho)-\epsilon = j^{\widehat\pi}(\widehat\lambda)-\epsilon. \tag{x}

Combining Eq. (ix) and Eq. (x), we obtain

J_N^{\mathrm{opt}}\ge j^{\widehat\pi}(\widehat\lambda)-\epsilon. \tag{xi}

The rest of the proof then follows the same line as the one after Eq. (55) in our paper.

AuthorsOpenReview ↗

Response to Q2

(Q2: Experiment setup of Figure 2 and Table 2 and other experiment details) We thank the reviewer for pointing out that the setup of Figure 2 and Table 2 are different. Indeed, Figure 2 is the AoI experiment with 600 arms, 200 activations and 600 time steps. In contrast (as discussed in Appendix K.2), table 2 are with 200 arms, 30 activations and 600 time steps. This choice of different set-ups was partly because the experiments of Table 2 involves environments beyond AoI. However, we understand that this change of experiment set-up may have caused some confusion. In light of this, we re-conduct experiments for Figure 2 using the same settings as Table 2: 200 arms and 30 activations, and update the paper pdf with this new figure. In this setup, the gap between DeepTOP and our parameter-driven pipeline is even larger. We report the mean index-error averaged across timesteps in Table I below. Table I. Mean index error averaged across timesteps.

MethodMean index error
WAC0.842
WQL1.187
DeepTOP9.881

Regarding the details of simulator-transition counts, training time, variation across runs, and the parameter distributions used for training and evaluation, we provide the answers below.

Regarding the simulation cost, WAC and WQL use the same simulation-transition budget, thus there is no extra simulation time for WAC. As detailed in Appendix D.1 (p. 17), WAC performs 2 value-function TD updates (batch size 16) and 32 rollouts of length 24, whereas WQL performs 25 Q-function updates (batch size 32), using freshly sampled transitions without replay. With 5 sampled environments and 12 states per environment (Ka=Kd=3K_a=K_d=3), the respective simulation counts are the same:

\begin{aligned} \text{WAC: }&5\times12\times(2\times16+32\times24)=48{,}000,\\\\ \text{WQL: }&5\times12\times(25\times32)=48{,}000. \end{aligned} \tag{xii}

Thus, the performance advantage of our WAC is not due to more samples, but because of the improved training method. We omit experience replay in WQL because it has led to less stable index learning in our experiments. One possible reason is that for index learning, we need to learn an accurate optimal Q-value for both actions, but imbalanced sampling from the replay buffer may impair Q-value estimation.

Regarding the training time, the training time for WAC (485485 seconds) is two times smaller than WQL's (910910 seconds). The reason that WAC is faster is as follows. Though the samples used for WAC and WQL are the same, the computation of WAC is simpler than that of WQL. Specifically, most of the samples used by WAC are consumed by the rollout, which is much cheaper since it only requires one forward pass of the value function network without the need of backward passes. In contrast, WQL requires 25 backward passes of the Q-network per index-update iteration. Under 5000 policy iterations and hidden width h=8h=8, WAC takes 485485 seconds and WQL takes 910910 seconds.

Finally, regarding the variations across runs, we have found that even after considering variation across each runs, the advantage of WAC over WQL is still evident. The standard deviation of corresponding to the results of Table 2 (the performance comparisons under different RMAB environments) is added in the table below. The results are averaged over 3 evaluation seeds. These results further demonstrate that the performance improvement of WAC over WQL is consistent across evaluation runs and is not merely due to random variations.

Table II.

TaskWACWQLDeepTOPRandom
AoI690.43 +/- 0.70692.78 +/- 0.74734.56 +/- 0.85733.75 +/- 0.89
Healthcare123.44 +/- 1.27126.71 +/- 1.92126.82 +/- 0.85148.57 +/- 1.44
Maintenance 1D981.47 +/- 6.101049.03 +/- 3.691287.26 +/- 5.461268.55 +/- 15.13
Maintenance 2D658.20 +/- 1.97734.71 +/- 9.31945.85 +/- 11.821092.91 +/- 8.35

The environment parameter distributions used in training are the same with that of used in evaluation. For AoI, (ps,pg)(p_s,p_g) is sampled uniformly from an 11×1111\times11 grid spanning [0.5,1]2[0.5,1]^2. For the other tasks, parameters are sampled uniformly from the following ranges: (pdrop,precover)∈[0.05,0.35]×[0.25,0.85](p_{\mathrm{drop}},p_{\mathrm{recover}})\in[0.05,0.35]\times[0.25,0.85] for Healthcare, (pup,prep)∈[0,1]2(p_{\mathrm{up}},p_{\mathrm{rep}})\in[0,1]^2 for Maintenance 1D, and (pdeg,pstress)∈[0.08,0.30]×[0.05,0.30](p_{\mathrm{deg}},p_{\mathrm{stress}})\in[0.08,0.30]\times[0.05,0.30] for Maintenance 2D. They are all consistent with the evaluation ranges. We will state it more clearly in the revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.