Multi-play Multi-armed Bandit Model with Scarce Sharable Arm Capacities

Thank you for your comment, and your questions will be answered one by one.

1. As for the mentioned confusing notations in the first weakness: (1) $\epsilon^{UE}$ is the correct notation; (2) the full name of the cited article is ''Tightening exploration in upper confidence reinforcement learning'';(3) the lemma used in the proof of Theorem 1 is the Theorem 14.2 in Lattimore$\&$Szepesvari(2020). This lemma is also mentioned in the proof of Theorem 3 and it is cited properly there;(4)The mentioned "MP-MAP-SA" should be "MP-MA-SE" actually;(5) A rebuttal version of the article is submitted and the writing quality is improved.

2. The question mentioned in the second term in the weaknesses part:(1) Sorry that we are not sure whether more examples or more concrete details on the LLM application are expected. We would appreciate it if you can give a clue on this. (2) Running an LLM service has cost on computing resource, IT operations of the system, system maintenance, etc. Transmitting an end user's query to the commercial LLM server has a communication cost, especially when a query has a long prompt input. The cost $c$ is an aggregate abstraction of the above cost. (3) More detailed analysis of the experimental results is proposed in Section 6 in the rebuttal version and Section A in the appendix.

3. The question mentioned in the third term in the weaknesses part: (1) The comparison is fair for the following three reasons. First, the comparison between the results of the example complexity is fair. The example complexity is focused on one particular arm, and the rank of arms is not included. Second, as for the regret bounds, consider the case when $M=N$, which satisfies the conditions in both Wang et al.(2022a) and this article. Then the optimal action is the same, and the rank of the arms is not required to be learned. It should be noted that the regret lower and upper bounds in Wang et al.(2022a) are reduced to $\Omega\left(\sum_{k}\log T\right)$ and $\Omega\left(\sum_{k}\left(w_k\sigma^2 m_k^2/\mu_k^2\right)\log T\right)$. Compared to the bounds in this article, their lower bound is less informative than the $\Omega\left(\sum_k\log T/\mu_{k}^2\right)$, while their upper bound is the same. Third, Wang et al calculate the regret by decomposing it into several parts. And the part that is related to estimating the capacities of the ''optimal arms'' is not related to ranking of the arms, and the part of regret related to estimating the capacities is bounded as it is shown above. So it is fair to compare the part that estimates the capacities in the regret bounds. (2) The word ''unstable'' might mislead you about the robustness of the algorithm. The actual meaning is that the denominators of the confidence bounds are preferred to be positive as soon as possible. Otherwise $N-\sum_{i=1,i\neq k}^K m_{i,t}^l$ will be the upper bound of the capacity, and this value is not a good estimation. Additional experiments are conducted to compare the convergence speeds of the two estimators

4. The question mentioned in the questions part: The article shows that the sample complexity gap is closed by UE and IE, in which the arms are assigned with UCB and LCB plays respectively. The closed sample complexity gap serves as clues that the regret bound gap in this problem can be closed by UE and IE as well.

Thank you for your comments, and your questions will be answered one by one.

1. First, the choice of studying the $N\geq \sum m_k$ case is mainly attributed to the fact that it is common in real world that the resources are scarce and the competition for these resources is intense. Second, it is not mentioned in the article that the $N\geq \sum m_k$ case is more challenging than the $N< \sum m_k$ case. You might be curious about the fairness of the comparison between results in both cases, and this question will be answered below.

2. (1) The comparison is fair for following three reasons. First, the comparison between the results of the example complexity is fair. The example complexity is focused on one particular arm, and the rank of arms is not included. Second, as for the regret bounds, consider the case when $M=N$, which satisfies the conditions in both Wang et al.(2022a) and this article. Then the optimal action is the same, and the rank of the arms is not required to be learned. It should be noted that the regret lower and upper bounds in Wang et al.(2022a) are reduced to $\Omega\left(\sum_{k}\log T\right)$ and $\Omega\left(\sum_{k}\left(w_k\sigma^2 m_k^2/\mu_k^2\right)\log T\right)$. Compared to the bounds in this article, their lower bound is less informative than the $\Omega\left(\sum_k\log T/\mu_{k}^2\right)$, while their upper bound is the same. Third, Wang et al calculate the regret by decomposing it into several parts. And the part that is related to estimating the capacities of the ``optimal arms'' is not related to ranking of the arms, and the part of regret related to estimating the capacities is bounded as it is shown above. So it is fair to compare the part that estimates the capacities in the regret bounds.(2) As for the equation 5, the returned reward of equation 5 contains less information as it is explained in line 79-85. And it is a reward model of conventional linear bandits with one dimensional feature, which is as common as the one with increased noise's variance. Moreover, we can get the corresponding regret lower bound with reward function as equation 1 in the same way, and the lower bound is modified by multiplying the term $\exp({-9TK/2})$. This implies that the problem setting with equation (5) is more difficult than that with equation 1. Consequently, if we can get a closed regret upper and lower bounds in the setting of equation (5), the same techniques or insights might work in the setting of equation 1.

3. That's correct. This bound is also a kind of rough bound, and we list it as a theorem for readers to find the similarity of this the upper bound and the one in Wang et al.(2022a). And your concern is solved in the rebuttal version. A new bound is shown explicitly as Theorem 7 at the last part of the appendix.

4. When the movement cost $c=0$, consider the case when there is almost infinite plays compared with the capacities. We can assign every arm with one play in the first round, and double the number of plays assigned to each arm after every round. Because of the absence of movement cost, once the number of plays assigned to arm $k$ exceeds the capacity $m_k$, there would be no regret. So the regret of this strategy remain constant after only a few rounds. This implies that there might be other strategies which optimize the action in much fewer rounds without learning the exact $m_k$. As for the next question, the results in sample complexity in Theorem 1 and Theorem 2 show that the sample complexity is independent of $m_k$. And in the proof of the lower bound, we can only assume that the regret generated by single exploration to be $\min(\mu_k-c,c)$. So it is reasonable for the regret lower bound to be independent of $m_k$.

Thank you for your comments and suggestions, and your questions will be answered one by one.

1. The $m_k$ is not known in advance. There is no requirement on the dependence of $m_k$ and $c$ in this article. The only requirement of the movement cost $c$ is that $c<\mu_k$ for all $k$, so that every unit of occupied resource is expected to increase rather than reduce the utility. This requirement is necessary in our proof, especially when considering the regret lower bound. Because it is demanded that both overestimating and underestimating the capacity $m_k$ should generate a regret.

2. The main reason is that there are not sufficient plays for every arm to be played with UE freely. Once there are enough plays to arrange UE on all arms, we can use Theorem 2 on each arm separately. When there are not enough plays, some arm are forced to be played with IE. According to the regret lower bound in Theorem 3 and Theorem 4, the larger $\mu_k$ is, the less time slots we have to spend on that arm to get $m_k$. Moreover, if the arm with large $\mu_k$ is forced to be played with IE because of the lack of plays, it will be likely that the regret can be large too ( we do not know $m_k$ in advance, so all we can do is using $\hat{\mu}\_{k,t}$ or $\hat{\mu}\_{k,t}m\_{k,t}^u$ or other estimators to predict the regret). In this algorithm and the proof of its regret upper bound, it is shown that $\hat{\mu}\_{k,t}$ is a qualified estimator.

3. The only reason for setting $c=0.1$ is to meet the requirement that $c<\mu_k$ for all $k$. The movement cost $c$ is known in advance in a practical scenario, and $c$ is independent of $\mu_k$. Additional experiments with different values of $c$ are conducted, and results are proposed in Appendix A.4.

4. There are changes in the range of $m_k$ in the appendix part A.1. And it is shown that the larger $m_k$'s range is, the larger the regret is. Additional experiments are done as you required, and you can check the figures depicting the impact of changing $c$ in the Appendix A.

Thank you for your comment, and your questions will be answered one by one.

1. For the first question, the answer is yes. If for some $k$ there is $\mu_k<c$, then the arm $k$ can not generate reward. In most real world cases, it is rare to see people paying to occupy resources and get nothing. So we can set the movement cost as a small value.

2. That is a mistake in notation. $\mu_k$ is set as $\mu$ here, which is the per unit reward of the arm $k$.

3. Sorry that I do not understand the question because there should be no dependence of the play number $N$ in the sample complexity, but I think you may be curious about the absence of $m_k$ in the upper bound of the sample complexity. Sample complexity here is the number of time slots demanded to calculate the true capacity $m_k$. The estimated UCB is not searched from $[N]$ randomly, but calculated with previous information generated by previous actions in the MAB. If the confidence intervals in Wang et al. (2022a) are used in this article, there will always be $m_k$ in the upper bound of the sample complexity. But with the refined confidence intervals in this article, the gap between upper and lower bounds is closed up. The sample complexity is different from the regret bound, and the regret upper bound depends on $N$. As for the cases when there is no noise, the upper bound of the sample complexity is actually $2$: one UE and one IE should suffice to get the correct capacity via dividing. So the complexity for all non-negative $\sigma$ can be modified by adding $2$, and this new upper bound is shown in the rebuttal version.