Summary
This paper presents a neural Q learning method to compute the Whittle indices in restless multi-armed bandit problems. The paper provides an algorithm using two-timescale stochastic approximation (2TSA) to update the parameters in the neural networks and the Whittle indices jointly with different learning rates. The authors also show that the 2TSA method guarantees convergence to the optimal/approximately optimal solution of Whittle indices. One of the major contributions is the breakthrough of not using projection step in the 2TSA algorithm. The algorithm proposed by the authors doesn’t require the functional class to contain the optimal functional approximator. The corresponding approximation guarantee also shows an additional term dependent on the distance of the true optimal to the span of the functional bases used in neural networks. Lastly, the authors provide experiments to show the convergence of the proposed algorithm and empirically verify the assumptions made in the paper.
Strengths
I like the idea of projecting the neural networks using ReLU to linear functions to enable downstream analysis. The paper also generalizes the theoretical analysis in previous work to quantify the impact of approximation error in the functional approximator class. I didn’t go through the appendix, but the proof sketch is clear to me. Overall, the paper is nicely written with new theoretical contribution compared to the previous work. It would be great if the authors can further emphasize and summarize the contributions in the theoretical analysis that are incurred due to not using projection steps. The convergence rate also matches the previous work using projection steps.
Weaknesses
The comparison to the previous algorithm is not clear. I didn’t fully understand why the previous algorithm requires a project step to force the parameters in a bounded set and why your algorithm doesn’t. I believe it is due to the analysis in the convergence guarantee where unbounded parameters can lead to useless bound or divergence. Could you please clarify and emphasis this in the paper more to highlight your contribution more clearly? Especially this seems to be the major contribution of the paper. It deserves a larger portion of the paper to clarify it.
Please also clarify why the definition of Whittle index is different from Whittle et al. and most of the literature. Please see below for more details. I am worried that the different definition can impact the convergence analysis (especially the linearity and Lipschitzness in the proof). Please either justify the use of your definition and any references showing this different definition is valid, or show us that the analysis is not impacted by the definition.
These two are my major concerns of the paper. Please clarify them and I am happy to update my score based on the response.
[Answered by the authors during the rebuttal]
Questions
**Question 1**:
Equation 3: the Whittle index defined by Whittle is defined as the Lagrangian multiplier such that the Q values of action 0 and 1 are identical, i.e., whittle index $\coloneqq \inf_\lambda \{ Q_n(s,1;\lambda) = Q_n(s,0;\lambda) \}$, where the Q functions are functions of lambda (Lagrangian multiplier) and thus parameterized by lambda. However, your definition in Equation 3 is defined as the difference between Q values, i.e., whittle index $\coloneqq Q_n(s,0) – Q_n(s,1)$, where the Lagrangian multiplier for defining the Q values is also not specified. To my knowledge, this is not equivalent to the original Whittle index definition. The original Whittle index is defined based on the solution to Lagrangian relaxation, but yours doesn’t have this property. Please clarify/justify why you can define Whittle index in this way or provide any references supporting your claim. And please also clarify how this definition impacts you downstream analysis.
I have also checked your references in [3,23] are also aligned with the original Whittle index definition (Whittle index defined such that Q(s,0) = Q(s,1)). Please see Equation (4) in [23] and Equation (11) in [3].
Equation (13) will also be impacted by the definition of Whittle index. So does the analysis in Equation (21) and Lemma 2, which will no longer be linear.
References:
[3] Konstantin E Avrachenkov and Vivek S Borkar. Whittle index based q-learning for restless bandits with average reward. Automatica, 139:110186, 2022.
[23] Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian & New Zealand Control Conference (ANZCC), pages 249–254. IEEE, 2019.
---
**Question 2**:
Do other choices of step size sequence $\alpha$ and $\eta$ work as well?
**Feedback 3**:
Equation 18 is the linearized version of Equation 6 where the coefficient associated to the linear term is defined by the initial point $\theta_0 = [w_{r,0}]$. The definition is correct but slightly unclear.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
- Different definition of Whittle index: if this is true, then the analysis might be restricted to the definition shown in the paper.
- Linearization: the authors need to linearize the Lyapunov function to enable the theoretical analysis. I believe this is the reason why the authors focus on 2-layer neural networks (only input and output and a ReLU activation function). This can limit the functional approximator class to such neural networks only. For more complex NN structures, the same linearization trick and analysis don't apply anymore.