Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper provides a simple modification on the best-of-both-worlds algorithm of Rouyer et al.  (2021) to achieve a logarithmic pseudo-regret bound in stochastically-constrained setting which improves $O(T^{1/3}/\Delta)$ bound of Rouyer et al.  (2021) to $O(\min ( \log T/\Delta^2, T^{2/3} ) )$, while achieving the same optimal regret bound for oblivious adversary setting. They also provide a lower bound for stochastically-constrained setting that shows the factor $1/\Delta^2$ is unavoidable.
strengths_and_weaknesses: Originality:

- The paper essentially has one general key idea which is to verify and decide when and how to switch to different algorithm, whereas this general idea has been used before to obtain best-of-both-worlds algorithms. While recognizing the type of environment and the time to switch is quite challenging in bandit, here determining when to switch is extremely simple. 
While the novelty of provided algorithm is questionable, I believe recognizing this fact that this simple modification is would works here in stochastically-constrained setting is quite interesting.
The analysis of the proof is very straight forward and uses Tsallis-INF bounds along with some bounds on switches which is again not a completely new novel analysis. Therefore the analysis has no special novelty.

- The lower bound part of the paper is basically based on the construction suggested by Dekel et al. (2014), whereas, it originally works for adversary setting and here the authors tried to adapt it to stochastically-constrained setting, as well. I may consider some novelties for the adaptation part but the analysis of it has no new idea and novelties.

Quality and Clarity:

- Generally the flow of paper and the analyses are clear and easy to follow. I tracked all the analysis steps and seems sound to me. However, there are some minor issues listed below. 

1. In Algorithm 1, I failed to find definition of learning rates $\eta_t$. I found the definition from Rouyer et al. (2021) but you must also include the definition in your paper as well. 
2. There are two typos in the analysis where you use  $S$ instead of $\mathcal{S}$ in proof of Lemma 5 (the second inequality between line 148 and 149) and in the statement of Lemma 6. 
3. The sentence that starts from line 121 to 124 is vague to me. I suggest to rephrase it to make it more clear.

Significance:

- Despite the simple trick used by the authors, the results is significant to me from two perspectives. First, they answer to the open problem arised by Rouyer et al. (2021) that asks if it is possible to obtain a logarithmic regret in stochastically-constrained setting with affirmative answer. Second, their lower bound indicates an essential difference between stochastic and stochastically-constrained settings. They show for the later setting the multiplicative factor $1/\Delta^2$ is unavoidable, whereas in a pure stochastic setting the optimal multiplicative factor is $1/\Delta$. 

The thorough discussion on the open problems is also considered as a strength of the paper.

The only thing about result that annoys me is that their algorithm requires knowledge of the time horizon in advance, while the previous work that theirs is upon that, needs no prior knowledge of the time horizon. There is no dicussion on the necessity of this assumption and what could be the cost of removing it.


questions: As I mentioned in the previous part, I want to see a dicussion on the necessity knowing time horizon in advance. More precisely, I want to know how your results would be affected by removing this knowledge?


limitations: There are two works where they refined the analysis of Tsallis-INF algorithm:
1. work by Ito (2021), where they remove the uniqueness assumption needed by the analysis of Tsallis-INF.
2. work by Masoudian and Seldin (2021), where they refine the regret bound of Tallis-INF in stochastically contained setting and intermediate regimes.

There is no discussion that what are the limitation that prevents the authors to get the same refinement here since their algorithm is based on Tsallis-INF.



Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In
Proceedings of Thirty Fourth Conference on Learning Theory, 2021.

Saeed Masoudian and Yevgeny Seldin. Improved analysis of the tsallis-inf algorithm in stochastically constrained
adversarial bandits and stochastic bandits with adversarial corruptions. In Proceedings of Thirty Fourth
Conference on Learning Theory, 2021.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the problem of achieving best-of-both-worlds in bandits with switching cost. Specifically, the authors design an algorithm that achieves O(T^{2/3}) regret bound when the loss environment is adversarial and $\min\{O(\frac{\log(T)}{\Delta_{\min}} (\sum_i \frac{1}{\Delta_i})), T^{2/3}\}$ regret bound when the environment is stochastically-constrained. The algorithm is based on a combination of classic FTRL with Tsallis-entropy regularizer and the block-wise update Tsallis-INF, which intuitively makes sense. The authors also show a lower bound of $\Omega(1/\Delta^2, \Delta T)$ in this problem when K=2. 
strengths_and_weaknesses: Strengths:
- The paper is nicely and neatly written.
- The algorithm is intuitive and presented in a very clear way. The analysis is also presented neatly. I check the analysis and they all look correct to me.
- The obtained results improve upon the previous work specifically in the bound for the stochastically-constrained case from $O(T^{1/3}/\Delta)$ to $O(\log(T)/\Delta^2, T^{2/3})$.

Weakness:
- I think there is no major technical issue for this paper. My main concern is the novelty of this work as the proposed algorithm is a simple combination of the known Tsallis-INF algorithm and the block-wise Tsallis-INF algorithm with a hard switch depending on the current number of switches of the algorithm. Lemma 6 looks interesting to me, which relates the number of switch to the regret but the remaining analysis is somewhat direct from the previous analysis. For the lower bound part, I think the modification from [Dekel et al., 2014] is also somewhat minor based on my understanding.

Minor typos:
- line 104: which demonstrate -> which demonstrates
- line 121: quite involve -> quite involved
- line 123: becomes quite -> become quite
- line 155: .Where -> , where
- line 137: I think the block size should be $\lambda^{2/3}K^{-1/3}T^{1/3}$ instead of the one with big O notation as you are using the exact constant in the regret bound.
questions: Could the authors explain more about the novelty about both the algorithm design and the lower bound proofs as for me, the two issues mentioned in Section 5.3 do not seem to be very difficult to handle based on the original proof shown in [Dekel et al., 2014].
limitations: Yes, the authors address the limitations of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the MAB problem with switching costs. The authors try to design a best-of-both-worlds algorithm, i.e., its regret upper bound is optimal for both the stochastic case and the adversarial case. In this paper, instead of the stochastic case, the authors consider a stochastically-constrained adversarial setting, in which the adversary needs to choose the losses from random distributions such that the expected loss of the optimal arm is always smaller than the sub-optimal arms by at least $\Delta$ at each time step. For this problem setting, the authors design an algorithm that achieves $O(\lambda^{1/3}K^{1/3}T^{2/3})$ regret upper bound in the adversarial case, where $\lambda$ is the switching cost, $K$ is the number of arms and $T$ is the time horizon. Existing results show that this is the best one can do in the adversarial case. As for the stochastically-constrained case, the algorithm can achieve a regret upper bound of $O({K\lambda \log T \over \Delta^2})$, and the authors also show that this regret upper bound is optimal (up to logarithmic factors) in the stochastically-constrained case by proving a matching regret lower bound.
strengths_and_weaknesses: 1. About the significance.

The best-of-both-worlds algorithms in the bandit setting attract much attention in recent years. The bandit problem with switching costs is also a well-motivated model. I also really like the natural idea of improving Tsallis-Switch by adding a start phase that runs classic Tsallis-INF and only changes to Tsallis-Switch if there are too many switches before. My main concern here is that "Switch Tsallis, Switch!" is not a fully best-of-both-world algorithm, i.e., it is best under the stochastically-constrained case but not the stochastic case. 

2. About the clarity.

Overall, the presentation is good and clear, though there are some typos that need to fix, e.g., 

- i) Line 51: "Notice, that" to "Notice that".

- ii) Line 83: "Where" to "Here".

- iii) Equation (3): missing a period in the end.

3. About the proofs.

I check all the proofs and they seem to be correct.

4. Some experimental results of comparison between "Tsallis-Switch" and "Switch Tsallis, Switch!" (for both the stochastic case and the adversarial case) would be helpful.



questions: 1. It is mentioned that in the stochastic case, [9,10] can achieve a regret upper bound of $O({K\log T \over \Delta})$. However, Theorem 2 shows that the regret lower bound for the stochastically-constrained case is $\Omega({K \log T \over \Delta^2})$. My question is that, in high-level ideas, what is the reason for this difference? Why is the i.i.d. assumption important to reduce the regret of bandits with switching costs?

2. This paper only considers the oblivious adversary. What if the adversary is non-oblivious?
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers the problem of bandits with switching costs and studies it in a best-of-both worlds setting. Bandits with switching costs have been extensively studied in both the adversarial and the stochastic regimes separately, but only recently considered in the the best-of-both worlds setting by Rouyer, Seldin and Cesa-Bianchi (2021).

The authors consider the same regime as Rouyer et al. and present a simple algorithm that achieves the same (minmax optimal) rate of $O((\lambda K)^{1/3}T^{2/3})$ pseudo-regret against oblivious adversarial sequences of losses, and a $polylog(T)/\Delta^2$ pseudo-regret against stochastically constrained adversarial sequences of losses. This is the first polylog type of bound for this regime. 
The algorithm that they propose uses the regular Tsallis-Inf algorithm until the cumulative switching cost becomes too large, which triggers a change of regime to a version of Tsallis-Inf played with blocks. This type of algorithms was initially studied by Auer and Chiang (2016) in order to design a a near optimal best-of-both worlds algorithm. In this problem, as the algorithm is aware of the switching costs, monitoring when to trake the change does not incur extra logarithmic factors because the algorithm can use the switching cost to know when to trigger the change of regime rahter than by having to estimate the regret. 

Furthermore, the authors derive a lower bound for the stochastically-constrained regime in $\tilde \Omega (\min(1/\Delta^2, \Delta T)) $, which shows that the dependency in terms of $1/\Delta^2$ is unavoidable, and highlights that for this problem, the stochastically constrained regime is more difficult than the stochastic regime (which is a special case of stochastically constraine adversarial regime).

They finish off by mentioning several open problems that highlight the difficult aspects of the problem.  Those include whether it is possible to improve the dependency on the suboptimality gaps when $K > 2$ (by a factor $\Delta_{min} / \Delta_i$ on each arm), whether is is possible to achieve some improved result when all the suboptimality gaps are equal and larger than $1/T^{2/3}$, and question what the lower bound for the purely stochastic regime would be in a best-of-both worlds setting. 

strengths_and_weaknesses: The main contribution if the paper is certainly the lower bound that they derived.  Showing that there is a difference between the lower bounds for the stochastic and the stochastically constrained adversarial regimes is a crucial step towards understanding best-of-all worlds types of results, not only for bandits with switching costs but possibly for other variations of bandits problems.

The lower bound proposed is not tight up to logarithmic factors. That bound generalizes the analysis in the adversarial regime (Dekel et al. (2014)) which also contained logarithmic factors.

The algorithm proposed is simple and surprisingly well suited for the task. Algorithms that start by assuming that they are in a certain regime and then switch to another regime in case those assumptions are broken have been analysed when looking at best-of-both worlds bandits (see Auer et Chiang 2016), but having access to the switching costs makes the analysis easier, thus not leading to any extra logarithmic factors.

This being said, one of the limitations of the algorithm is that it may not be well suited to generalizations of the problem.
In this paper, it is assumed that the best arm is unique. This assumption is not trivial in the case of bandits with switching costs, because in presence of several optimal arms, the algorithm may often switch between those optimal arms often, which may lead to a a large cumulative switching cost, and thus would force the algorithm to switch regimes early, leading to a $O(T^{2/3})$ type of regret. [Note that while it was originally unclear whether Tsallis-Inf could handle several optimal arms, it has been shown recently (Ito (2021)) that Tsallis-Inf can handle several optimal arms]
Also, the algorithm requires the time horizon to be known by the learner. It is likely that some type of doubling trick could be used to estimate the time horizon, but choosing the rate at which the time horizon increases may lead to logarithmic factors in at least one of the regimes. 

The paper is clearly written and compact.


questions: Have you thought about the points discussed in the previous section? Namely about the unicity of the best arm and the required knowledge of the time horizon?


limitations: Theoretical work, so societal impact is N/A.

The paper is clear with the assumptions that are made for their results to apply, and the capacity to generalize those assumptions has already been mentionned earlier.
review_title: null

Meta-review: metareview: Reviewers all agree that this is an interesting work with significant contribution to the best-of-both-worlds literature. Clear accept. Please do still address the minor issues pointed out by the reviewers in the final version.
confidence: Certain
Decision: Accept