Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work studies adversarial reinforcement learning with switching costs in the tabular setting. This work designs the super-episode containing $\tau$ episodes and proposes an occupancy measure-based algorithm SEEDS. To control the switching cost, SEEDS uses the same policy in a super-episode and only updates the occupancy measure at the last of each super-episode. As the first step, this work proves the lower bound $\tilde{\Omega}((HSA)^{1/3}T^{2/3})$ in this setting. By carefully choosing $\tau$ to balance the loss regret and the switching cost, this work proves SEEDS achieve $\tilde{O}((HSA)^{1/3}T^{2/3})$ regret guarantee which matches the lower bound with the known transition. With the unknown transition, SEEDS-UT almost matches the lower bound within a factor of $\tilde{O}(H^{1/3})$.
strength_and_weaknesses: Strengths: 

This work is the first to deal with the switching cost in adversarial RL. The algorithm in this paper (almost) matches the lower bound if the lower bound is correct. 

Weakness：

1. The definition of the switching cost is unreasonable. In this paper, as long as the policy distribution changes slightly, there will be a switching cost. Imagine that if $\pi_{t+1}$ and $\pi_{t}$ are only slightly different (for example, a small KL divergence), we can fine-tune the policy. Then we can use offline evaluation methods such as importance sampling to evaluate the new policy, and there is no need to pay a high cost.

2. The analysis of the lower bound in this paper is confusing. As stated in Weakness 1, the indicator function consider whether the policy distribution $\pi_{t+1}$ and $\pi_{t}$ are different, not $a_{t+ 1}$ and $a_{t}$ are the same. However, for adversarial bandits with switching costs, the indicator function considers whether $a_{t+1}$ and $a_{t}$ are different. These are two completely different measures, so the lower bound proved by Shi et al. (2022) cannot be used directly.

3. I did not see too many difficulties in the regret analysis process of Theorem 4. It seems that the proof process of Theorem 4 is a standard online mirror descent (OMD) proof process, except that super-episodes replace episodes. It is worth describing the non-trivial tricks of the proof process.

4. The core components of extending known transition to unknown transition are exactly the same as Jin et al. [2].

[1] Shi, M., Lin, X., & Jiao, L. (2022, October). Power-of-2-arms for bandit learning with switching costs. In Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (pp. 131-140).

[2] Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp. 4860–4869. PMLR, 2020.

Question:

Q1: Can you explain in detail why you can use the lower bound proved by Shi et al. (2022) directly?

Q2: Can you propose a more reasonable way to measure the difference between the two policy distributions and prove an upper bound? 

----

It seems that the authors indeed work with deterministic policies. Then the setting and lower bound make sense to me. Though I still feel that the techniques are a bit incremental, it is not a fundamental issue. I would like to increase my score to 6.
clarity,_quality,_novelty_and_reproducibility: Quality: The proof in this new setting is correct.

Clarity: This work is well-organized.

Originality: This work is the first to deal with the switching cost in adversarial RL. However, the proof process is similar to the previous works. Hence I think this work represents incremental advances in a new setting.

summary_of_the_review: This work proposes an occupancy measure-based algorithm SEEDS using super-episodes and (almost) matches the lower bound. However, the definition of the switching cost is not very reasonable. Furthermore, the proof of the lower bound is a bit confusing. The lower bound proved by the previous work can not be directly used in this work. Finally, the technique when proving the upper bound is almost the same as the standard proof process of online mirror descent and the proof process of the previous work [2].
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of online reinforcement learning with adversarial losses and switching costs, where there is a cost for switching the policy during learning. The main result is an algorithm that achieves $\tilde{O}(T^{2/3})$ regret and switching cost, for both the setting of known and unknown transitions. The paper also provides a matching $\Omega(T^{2/3})$ lower bound.
strength_and_weaknesses: Strengths:
 * The topic of the paper should be of good interest to the community. The paper focuses on Adversarial MDPs (AMDPs), an MDP with fixed (unknown) transition and adversarial reward/loss functions, which can be viewed as a tractable adversarial analog of standard stochastic MDPs. Studying the switching cost problem has been done in both adversarial bandits, and stochastic MDPs. Thus a first result on switching cost in adversarial MDPs is definitely of interest.

* The obtained result of $\widetilde{O}(T^{2/3})$ regret and switching cost is solid, matches the result in adversarial bandits and slightly worse than in stochastic MDPs, which are expected. The result is established in both the known transition setting, and the unknown transition setting (which in my opinion is the main interesting one). 

* The paper is extremely clearly presented and quite easy to follow, with many intuitions discussed in detail and the related work adequately discussed. The paper could be a good reference point in the future for AMDPs and switching costs in adversarial settings. 


Weaknesses:

* The main concern is that, at the heart, the technical contribution of this paper may be a bit incremental—The entire algorithm seems to be a direct combination of the standard way to do adversarial bandits with switching costs with $T^{2/3}$ regret using the “batched” EXP3 algorithm, and the algorithm of Jin et al. (2020a) to learn AMDPs with unknown transitions. I feel the combination is direct, because this “batched EXP3 algorithm” for bandits can be done with fixed, equally-sized batches, and thus when applied in AMDPs, across different states, the policy switches can be straightforwardly synced, as done in Algorithm 1 & 2.  
In particular, this is comparatively easier than logarithmic switching cost bounds in the stochastic MDP setting, where the low switching mechanism is an exponential grid depending over the visitation count, thus has to be done asynchronously for each state. 

* Related to the above concern, I feel like the presentation of many technical intuitions are slightly over-repetitive and perhaps a bit overclaiming. As an example, the “novel idea for estimating the loss” part on Page 6, the provided baseline is indeed not quite sensible and non-standard, as the losses change in each episode. The provided solution instead, in Eq(8), is just averaging of importance-weighted loss estimator in standard EXP3, and seems a natural/standard practice to me instead of a really novel idea. On this end, I think it’s probably good to shorten the discussions of these standard practices, and expand on the more nontrivial bits (for example, an explanation of how the $T^{2/3}$ regret is achievable in bandits for readers not familiar with that, and/or how that integrates with the AMDP algorithm of Jin et al. (2020a) to give the final result).

clarity,_quality,_novelty_and_reproducibility: Please find my comments in the above “strengths and weaknesses" section.
summary_of_the_review: Overall, the paper obtains solid and interesting results for learning AMDPs with low switching cost, and is very clearly presented. However, I feel like technically it’s a bit incremental and unclear how the proof techniques could inspire future work.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work focused on adversarial MDPs with switching costs. The author proposed the SEEDs algorithms and provided a $O(T^{2/3})$ regret guarantee for both known and unknown transitions. In addition, the author also provided a theoretical guarantee for the lower regret bound, which suggests the proposed SEEDs algorithms are near-optimal on adversarial MDPs with switching costs.
strength_and_weaknesses: Strength:

The author provides the first analyses on switching costs in adversarial RL, and proposed novel algorithms SEEDs with $O(T^{2/3})$ regret guarantee for both known and unknown transitions. In addition, the theoretical lower bound shows that the proposed SEEDs algorithms are near-optimal.

Weakness:

Some of the paper’s claims need to be clarified.

1. The theoretical lower bound in Theorem 1 highly depends on the switching coefficient $\beta$, and when $\beta$ is small (e.g., $0$ or $O(1/T)$), the lower bound is smaller than $O(T^{2/3})$. Thus, it seems necessary to indicate the coefficient $\beta$ in the abstract and introduction.

2. The theoretical lower bound in Theorem 1 requires the number of episodes $T$ to be large enough. Otherwise, the lower bound is larger than $\Omega(T)$.  

3. For the related work, there exist different assumptions for the MDP. More specifically, the adversarial MDP assumes the state in each stage $h$ is non-overlap, and static MDP does not make this assumption. Therefore, it is better to indicate this difference for a fair comparison between related works.
clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to follow. However, the lower bound in Theorem 1 is just a simple extension from bandit to MDP. The novelty of the lower bound seems limited.
summary_of_the_review: The author provides the first analyses on switching costs in adversarial RL, and proposed novel algorithms SEEDs with $O(T^{2/3})$ regret guarantee for both known and unknown transitions. In addition, the theoretical lower bound shows that the proposed SEEDs algorithms are near-optimal. Although some of the paper’s claims need to be clarified, they can be easily fixed with minor changes.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies adversarial reinforcement learning (RL) with switching costs in an episodic setting, where a constant switching cost is incurred whenever the agent deploys a different policy. The authors first show a $\Omega(T^{2/3})$ regret lower bound, which generalizes the regret lower bound for adversarial Multi-Armed Bandits (MAB) with switching costs. Then, they propose two algorithms, SEEDS and SEEDS-UT, which can achieve provable regret guarantees. The first algorithm, SEEDS, requires the exact knowledge of transition probabilities and can achieve a regret that matches the regret lower bound. The second algorithm, SEEDS-UT, does not require the knowledge of transition probabilities. Its regret almost matches the lower bound with a gap of $H^{1/3}$, where $H$ is the length of each episode.
strength_and_weaknesses: Strength:

This paper makes solid contribution to adversarial RL with switching costs. While the regret lower bound result is not very surprising because similar lower bounds have been shown for the special case of adversarial bandits, it is good to see that the regret upper bound can match the lower bound exactly in terms of $T, H, S, A, \beta$ (episode number, episode length, state space size, action space size, and switching cost weight) when the transition probabilities are known. The authors also make their algorithm more practical by replacing the exact probability with an empirical estimator.

The paper is well-written and easy to follow. The authors add adequate discussions about the inspiration from previous works, and state the major technical difficulties clearly.

Weakness:

1.The proofs are not written clear enough for me to verify the results. For example, in the proof of Theorem 1 in Appendix A, what is the transition probability in this example? And what do you mean by the order of states?

2.It is not clear whether the proposed algorithms can be implemented efficiently, because the authors do not elaborate on how to compute equation (10). I conjecture the complexity will be high because the set $C(P)$ can be complicated given that it needs to consider all possible policies. This issue might become worse when the transition probability is unknown, because the estimation of transition probability is keep changing.

3.I feel the problem setting of adversarial RL with switching costs is closely related to online control, but that literature is not included in “Related Works”. Specifically, I feel the stronger regret performance metrics in that literature, like the dynamic regret or the adaptive regret, can work better than static regret in the non-static environments like adversarial RL. I recommend the authors to add a discussion in revision.

clarity,_quality,_novelty_and_reproducibility: As I discussed for the last question, the main body is written clearly but the writing in the proofs needs to be improved. As for the novelty, I feel the most original part is the design of SEEDS algorithm. In contrast, the lower bound result and the extension to the unknown transition probability (using the empirical estimators) are small modifications based on previous works.
summary_of_the_review: In summary, this paper makes solid contribution to adversarial RL with switching costs by providing the first matching regret upper and lower bounds. Compared to the significance of the contributions, the weakness I mentioned are not major concerns. Therefore, I recommend for accept.

Since the proofs are not carefully checked due to presentation issues and time limit, I prefer to choose a low confidence level.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies RL with switching costs under the model of MDP with adversarial rewards. The goal is to design an algorithm that minimizes regret against the best fixed policy in hindsight. A switching cost --- defined as the number of times the chosen (deterministic) policy selected by the learner changes --- is added as part of the loss function (thus the regret).

The result shows that  T^{2/3}  regret is optimal with a lower bound and an algorithm that achieves this regret under both known and unknown transition settings. 

The results are interesting as it separates the adversarial reward case with the stochastic reward case. Qiao et al. (2022) from ICML this year showed that one can obtain an $\tilde{O}(\sqrt{T})$ regret with $O(HSA \log \log T )$ switching cost and  \tilde{O}(T^{2/3}) regret with a constant $O(HSA)$ switching cost.   This paper shows that if the rewards are adversarial, there is a harsher tradeoff between learning and switching cost.  

In terms of weaknesses, reviewers found that the proof techniques used in the paper mostly from existing work modulo minor modifications. There was also some confusion initially regarding whether the current paper works with deterministic or randomized policies which could affects the correctness of some of the proofs.  This got cleared up in the discussion and the reviewer who raised these questions is convinced that the proof will go through with deterministic policies.
justification_for_why_not_higher_score: The topic is a niche for an ICLR audience but I think the story on the separation from the stochastic setting and the price of adaptivity is quite intriguing. It could be an interesting talk.
justification_for_why_not_lower_score: The paper provides a clean solution that settles a theoretical problem of practical relevance.  The results are new and correct.
Decision: Accept: notable-top-25%