- 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
- The paper has a clear use case as its target application (wireless scheduling) indeed suffers from frequent environmental changes.
- Simulation results show that its algorithm is better than DeepTOP.
Critical weaknesses
-
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.
-
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.
-
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
Response to Weakness 1 (Part 2)
(W1: The novelty of WAC, Part 2/2)
Let us denote 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 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.
| Method | Final index error |
|---|---|
| Using Original gradient, Eq. (6) | 0.5403 |
| Using Modified gradient, Eq. (7) | 0.2384 |
| Using Modified and rollout | 0.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 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 compared to the original gradient. With an additional rollout, it further reduces to only 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.
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 and parameters, where we fix the environment encoder's output dimension to be . 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.
| Methods | WAC | WQL | DeepTOP | Random |
|---|---|---|---|---|
| 6 parameters env | 657.84 ± 5.69 | 666.28 ± 4.38 | 794.83 ± 5.02 | 953.46 ± 1.57 |
| 10 parameters env | 508.58 ± 7.05 | 538.92 ± 10.15 | 620.40 ± 4.93 | 764.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 in Eq. (3) of DeepTOP is similar to in Eq. (6) of our paper, it only means that the two policies being evaluated differed at state (or ). The initial state distribution is still uniform, and thus Eq. (3) is not the same as Eq. (7) in our paper, which uses 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 represents a state and is the initial distribution. Note that the RHS of Eq. (v) is similar to the RHS of Eq. (vi), with replaced by .
To understand Eq. (vi), consider two policies that differ at state . Regardless of the initial state distribution , the difference of value function (left hand side of Eq. (vi)) can be written as the “visitation measure ” multiplied by the Q-function difference at state . Hence, it is clear that both of Eq. (v) and of Eq. (vi) inside the Q function correspond to two policies taking different actions at state (or ). Note that this is independent of the initial time distribution .
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 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 in Eq. (vii) is replaced by 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 , instead of the uniform . This modification is important for training: without this modification, the original gradient is too small and training is unstable.
In summary, even though in Eq. (3) of DeepTOP appears to play a similar role as 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.
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(μϕ) 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, θ is the Q-network parameters; the latter θ′ is updated by an exponential moving average of θ. [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 argmaxaQ(s′,a) (line 101).However, the confusion arises because, even though the two Qλ(s,a) share the same notation, they stand for very different meanings. The Qμϕ(s,a) in Eq. (i) represents the Q-function with respect to the current threshold policy based on the index values μϕ(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′ is reached, the corresponding action is supposed to be determined by 1μϕ(s′)>λ, which is exactly the threshold policy based on the current index values μϕ(s′). In contrast, Qλθ(s,a) used in Eq. (ii) is the Q-function of the optimal policy since in Eq. (ii) there is a max operator. Since these two Q-functions are different, substituting the Qλθ(st,at) learned from Eq. (ii) into Eq. (i) does NOT optimize the original actor-critic objective K(μϕ). 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.)