Model predictive control is almost optimal for restless bandits

We would like to thank the reviewer for the encouraging comments and score.

Rev Are there any comparison on the running time of different algorithms, and your algorithm with different $\tau$?

In the submitted version of the paper, we do not compare the running time of our algorithm as a function of the parameters. One of the reasons for that our code uses a non-optimized Python implementation and we strongly believe that they are a lot of optimization that could be implemented to make our code run faster. Still, a quick benchmark seem to indicate that the computational complexity of our implementation grows around $\tau^2$: to compute one point of control, it takes a few milliseconds to solve the problem when $\tau=10$ and around $0.8$ seconds when $\tau=100$.

Rev: Are there any experiment on real-data?

Anwer As our paper is theoretical by nature, we do not made experiments on real-world data. Note that such experiments are rather uncommon in papers presenting theoretical results on restless bandit problems.

Rec: In which part of the proof shows that $\tau(\epsilon) = \mathcal{O}(1/\epsilon)$?

Answer Note that the asymptotic convergence result stems from $\sum_{t = 1}^{\infty} L_{t}(x) - L_{t - 1}(\Phi(x, u)) < \infty$ is bounded and $L_{t}(x) \geq L_{t - 1}(x)$. This means we have an infinite sum of non-negative numbers, hence, the $t^{th}$ term must "on average" fall faster than order $1/t$. A more technical way of writing the result may be to say that for a sequence of $\epsilon_i \to 0$, picking $\tau(\epsilon_i) = C/\epsilon_i$ results in $L_{\tau(\epsilon_i)}(x) - L_{\tau(\epsilon_i) - 1}(\Phi(x, u))$ being "frequently in" a ball of radius $\epsilon_i$ but such a statement would be needlessly difficult to read for an uninitiated reader.

We would like to emphasize that some of the criticisms made are not correct, and in particular the points 2 and 4 below.

Rev (1): On one hand, the LP based relaxation has been extensively used in the RMAB literature, such as Verloop 2016, Zhang and Frazier 2022. On the other hand, the randomized rounding procedure is almost the same as that in Gast et al. 2023a and a finite-horizon MPC algorithm (LP-update policy) was proposed in Gast et al. 2023a,b. It is more like a straightforward extension. From the algorithmic perspective, can you more explicitly state what you see as the key novel aspects of the MPC based algorithm compared to prior work, particularly Gast et al. 2023a,b.?

Answer: We thank the reviewer for the comment. The algorithm itself has been well established, the novelty lies in proving that a finite horizon LP-update policy returns an asymptotically optimal solution to an infinite horizon problem under minimal assumptions. Please take a look at the general comment for more details.

Rev (2) The first result in Section 4.1. This is not surprising and it is commonly known in the RMAB literature that LP-based method for RMAB is provably asymptotically optimal. Indeed, the LP based method has been leveraged to design index policy for RMAB problem without the hard-to-verify indexability condition as required by the Whittle index policy, and such a LP-based method to design index policy is provably asymptotically optimal as shown in the literature, e.g., Verloop 2016 is one of the first works in this domain. Can you discuss how your result in Section 4.1 advances the state-of-the-art beyond what was already known from works like Verloop 2016? Are there any aspects of your analysis or bounds that are novel or improved?

Answer: We do not agree with this criticism by the reviewer. Yes, Verloop 2016 proposes a solution that does not require indexability, but this paper requires the condition ``UGAP'' that is known to be very difficult to verify. Moreover, Verloop 2016 does not provide a rate of convergence. See our "general comments" for more details.

Rev (3): The second result in Section 4.2. Likewise, the proof is directly from Gast et al. 2023a and Hong et al. 2024a. For both results, can your clarify exactly how the use of dissipativity differs from or improves upon previous approaches? can you discuss any limitations of previous methods that your approach overcomes?

Answer: With regards to Section 4.2 we note that due to the results from section 4.1 and continuity of the rotated cost function, we can conclude that the LP-update policy does steer the state towards the fixed point only by assuming the uniqueness of the fixed point. Hence, while parts of the proof are adapted from Gast et al. 2023a and Hong et al. 2024a, the two main steps that allow us to conclude that the state will lie in a local ball around the fixed point after a finite time are entirely an outcome of our dissipativity idea. This should be compared to the proofs in Gast et al. 2023a which assumed UGAP or Hong et al. 2024a which assumed local stability of the policy and aperiodicity of the transition kernel induced by the policy to make this claim.

Rev (4): In practice, how to determine how many arms to pull at each time, given that may not be an integer? If it is not an integer (may consider as an average constraint, there is no need to design an index policy). -Equation (3) itself is not a RMAB problem. It should be properly defined with the budget constraint to be satisfied at each time. It may be better to rigorously define (3)

Answer. We think that there is a missunderstanding: When looking at the randomized rounding policy (in our appendix), it clearly uses the floor function whenever $\alpha N$ is not an integer and this is reflected in the bound for Theorem 4.1. The reviewer should note that in the paragraph above equation (2) we clearly restrict our policy space to policies that are stationary and satisfy the budget constraint of pulling at most $\alpha N$ arms. This definition of the policy space $\Pi^{(N)}$ characterizes the Restless bandit problem.

Rev (5): There are many typos in the paper.

Answer: We thank the reviewer for pointing out the typos and will make an effort to correct them.

Dear Reviewer WFmj,

We would like to thank you for your thorough review of our paper. We encourage you to take a careful look at our responses since it seems there are a number of misunderstandings regarding our technical contributions as well as its place in the current literature of restless bandits. In particular we encourage you to take a look at our response to point 2 and 4 in our rebuttal. As the time for open discussions are coming to an end, we hope that you can respond to our replies or provide more points that might need to be addressed in our paper. We are hoping that our thorough response may have cleared some of your concerns and would like to encourage you to please reconsider your score. If there is any clarification that we could add, please ask.

Our main comments concern question (2) below for which we do not agree with the critic.

Rev (1) My main concern is that the order of gap has been a well-known result for a long time, which various types of algorithms can achieve. In particular, the LP-based algorithms in many related works cited by this submission without an additional MPC layer can also achieve this optimality gap.

Answer We agree that we do not improve on the $O(\sqrt{N})$ in the general case. Yet, we provide an algorithm that has many advantages:

• It is remarkably simple and is very easy to implement without requiring difficult to tune parameters.
• It has the same $O(\sqrt{N})$ guarantee (that is tight for our benchmark) in what seems the most general setting so far.
• It performs extremly well in practice.

Rev (2) Though the reviewer admits that the proposed MPC layer can bring some advantages, the key reason that this reviewer does not champion this paper is that there is a new work (https://arxiv.org/pdf/2410.15003) recently has pushed the gap to the order $\mathcal{O}(1/N)$ of by using a diffusion approximation technique. I understand that the authors submitted their work earlier than this recent work and may not be aware of this new work, the main concern always holds as the proposed MPC-based algorithm does not improve the well-known optimality gap.

Answer We do not agree with this criticism, for multiple reasons:

1. First, as pointed out by the reviewer, the paper https://arxiv.org/pdf/2410.15003 appeared after our submission. Hence, this paper should not be considered as related work.
2. Second, even if it is, the problem studied in https://arxiv.org/pdf/2410.15003 is that of a degenerate finite-horizon problem. Our seting (average reward) concerns the infinite horizon problem. These two problems are not equivalent, in fact, in the absence of further assumptions (for e.g. UGAP) or our own proof techniques, the divergence of the finite horizon solution can be order exponential in the horizon (see for e.g. the value of the Lipschitz constant in Gast 2023 b). A natural follow up question might be, can Yan's method be appended to our own to achieve the same results? The answer to this is quite unclear: Yan et al's work requires a second $H$ horizon stochastic program solution, showing that such a solution satisfies the dissipativity property is highly non-trivial. Therefore, if reviewer's main concern is that an $\mathcal{O}(1/N)$ algorithm has already been discovered, they can rest assured that this does not hold under the infinite horizon average reward setting. We encourage the reviewer to reconsider their score.

Rev: (3) Resolving the LP at each time step is not really a novel idea, which can be found in multiple works in related work cited by this submission. Though controlling is new, resolving LP at each time step causes a significant amount of computational complexity. Aligned with my first concern, why do we need such a complex algorithm that does not even improve the theoretical guarantee, which is claimed as a main contribution in this work?

Answer. We think that the beauty of our solution is that ``it suffices to solve the natural LP at each time to obtain asymptotic optimality in the most general setting''. We refer to our answer to point (1) and our general comment on the novelty of our result.

Rev (4): In many real-world applications that can be modeled as an RMAB framework, the underlying MDP for each arm may not be known in advance. My question is how can we leverage the proposed MPC-based algorithm for such a setting?

Answer We thank the reviewer for raising an interesting question. Our results can be used in model based reinforcement learning algorithms. For example: by using optimism in combination with our results on finite time horizon problems to approximate an equivalent cost function. It should be noted that we have shown the asymptotic convergence of the finite horizon rotated cost problem to the infinite horizon problem in our proof of Theorem 4.1 using dissipativity. This is an interesting line of future work which we intend to explore.

Rev (5): This paper considers a homogeneous arm setting. The reviewer quite doubts the scalability of the proposed algorithm when arms are heterogeneous and the number of arms is very large.

Answer: The reviewer raises another very interesting question. We would like to politely disagree with regards to the scalability issue in the heterogeneous case. We strongly suspect that our solutions can be used to come up with index based policies for the heterogeneous case but we do admit that we do not, as of this moment have a proof for this problem. This is a direction we are currently exploring.

Dear Reviewer QiUV,

We would like to thank you for your review, comments and excellent questions. We have tried to answer your questions as well as address your main concern regarding the rate of convergence of the optimal algorithm for the infinite horizon problem. As the time for open discussions are coming to an end, we would like to heavily encourage you to take a look at our response and let us know if there are any further questions that we may address. We would also like you to reconsider your score as we believe that your main concerns regarding our paper are unfounded. If there is any clarification that we could add, please ask.

Rev: In Section 6, the algorithm LP-priority is not formally introduced. It is confusing to distinguish between the LP-update and LP-priority algorithms due to the lack of a clear definition.

Answer: We thank the reviewer for the comment, we will make changes to our simulation results to address their comment.

Rev: What are the main technical contributions of the theoretical analysis compared to existing works? I suggest highlighting the novelty and primary contributions of the theoretical analysis more clearly.

Answer: Please refer to the general comment regarding our contributions. One of our the main technical novelties is the use of the dissipativity framework to analyze model predictive control in the restless bandit context.

Rev: In Line 88, the paper states, ``It performs well both in terms of the number of arms N as well as the computational time horizon T, beating state-of-the-art algorithms in our benchmarks." However, in the numerical experiments section, the authors did not compare the computational efficiency of the proposed MPC approach with existing algorithms. Moreover, it would be beneficial to provide a more rigorous discussion on why the MPC approach reduces the computational burden.

Answer: We agree that we do not discuss explicitly the computational complexity of our solution. The main reason for not providing measure of the time complexity is that we use a simple python implementation that we did not try to optimize. Yet, to give an order of magnitude, in all of the examples studied, the time to compute one control is around a few tens of milliseconds.

Dear Reviewers,

In light of your reviews we have made a few changes to our draft. Firstly, we have gone over and tried to correct typos where we could find them as well as modified some sentences slightly to reduce space consumption or slightly improve the phrasing. Such changes are not highlighted in a different color. Secondly, we have inserted a few major changes, these changes are highlighted in blue in our new draft. Of particular importance is the change made on page 2 which highlights the place of our work in the current literature. This is in accordance to the general comment we made to all the reviewers, the other comparisons can be found in the additional related works section in Appendix A.

Thank you.