Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a new bonus design mechanism, and utilizes it to derive new policy optimization algorithms with improved rates for adversarial MDPs. 
main_review: This is an interesting paper for the following reasons.

1. The paper is well written. The mechanism of the  bonus design and its technical motivation is clearly explained in Section 3. 

2. Implementing the dilated bonus on tabular MDPs gives a new policy optimization algorithm with $\sqrt{T}$-regret, which improves over Shani et al., 2020. All other known algorithms with the same rate [e.g., Jin et al., 2020a] requires solving a large-scale convex optimization problem over the occupancy measure per episode, while the algorithm in this paper doesn’t because of its clever ‘local’ bonus design. I checked the proofs for Section 3&4 in details, and I believe they are correct.

3. The authors further apply their bonus technique to adversarial linear MDPs and obtain improved results over prior arts.

Overall, this paper made solid technical contributions by designing more efficient algorithms with improved rates. 

Minor suggestion on related works:

The idea of adding $\gamma$ in the denominator of $\hat{Q}$ is actually first proposed in [1], which not only encourages exploration but also makes it possible to obtain high-probability bounds. If I remember correctly, [1] also proves some lemma that is highly similar to Lemma A.2 in this paper. 

[1] Explore no more: Improved high-probability regret bounds for non-stochastic bandits, Gergely Neu, NIPS 2015.

limitations_and_societal_impact: This work is purely theoretical. I am not aware of any potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies reinforcement learning in adversarial MDPs with policy optimization algorithms. Using a novel bonus design, the new algorithms achieve $\tilde{O}(S\sqrt{AT})$ regret in the tabular case, and $\tilde{O}(T^{2/3})$ regret in the linear function approximation case, assuming access to a simulator, significantly improving known results.
main_review: The key algorithmic idea of this paper is the following observation: suppose the regret with respect to $l_t-b_t$ can be bounded the loss of the optimal policy on $b_t$ (which can be large), one can cancel this term via linearity and bound the target regret with the loss of $\pi_t$ on $b_t$ (which can be controlled using standard techniques). This however requires $b_t$ to be designed in a "circular" fashion, which the authors resolve by using dilated bonuses. The new regret decomposition and bonuses are novel and interesting.

In the tabular case, the main result is an $\tilde{O}(H^2S\sqrt{AT})$ upper bound, which improves existing upper bound for policy optimization methods. Although it is one $H$ factor away from the current best result for adversarial MDP with bandit feedback [Jin et al. 2020], it enjoys a better computational efficiency. In the linear function approximation case, the first result is an $\tilde{O}(T^{2/3})$ regret bound assuming access to a simulator, which is the first known sublinear result of its kind. Although access to a simulator is usually a strong assumption, it can be justified since it is required by existing work on adversarial MDPs or even stochastic MDPs [Lattimore et al. 2020]. Other results include a $\tilde{O}(\sqrt{T})$ rate assuming an exploratory policy, and a $\tilde{O}(T^{6/7})$ rate assuming exploratory policy and linear MDP (but removing the need of a simulator). The exploratory policy is also a strong assumption, but is also assumed in existing work to achieve sublinear regret in adversarial linear MDPs. Overall the results of this paper seem to be solid contributions to the existing literature.

Other comments:

- The number of queries to the simulator is larger than $A^H$ but is not reflected in the regret bound, which is different from the stochastic settings where queries to the simulator is regarded as the sample complexity. In stochastic MDPs, with $A^H$ samples of uniform exploration, one can already evaluate any policy via Monte Carlo. The reason why this doesn't help in adversarial MDPs seems to be that the simulator does not return reward information. This makes one feel that the role of simulators in adversarial MDPs with linear function approximation (with bandits feedback) is a bit odd: the algorithm cannot extract reward information (as per Assumption 2) and cannot learn the dynamics as the state space can be infinite.

-  If the state space is finite and if one allows an infinite budget of queries, one may treat the dynamics as known and evoke existing results (e.g. [Neu et al. 2010]) whose regret bound are independent of the number of states. Thus there seems to be a trade-off between simulator query complexity and online regret, and it would be interesting to know where $A^H$ is positioned in this trade-off.

- In the algorithm box of Algorithm 2, the reference to Algorithm 6 should be Algorithm 7.

-------
Neu et al. The online loop-free stochastic shortest-path problem. 2010.

Lattimore et al. Learning with Good Feature Representations in Bandits and in RL with a Generative Model. 2020.
limitations_and_societal_impact: This work is purely theoretical and do not present foreseeable negative social impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper makes several contributions: 
	
1. In the episodic tabular setting, with adversarial rewards, unknown MDP dynamics and bandit feedback, it provides the first algorithm that achieves O(\sqrt T) regret bound using the regret decomposition approach, which is more computationally cheap than the approach presented in Jin et al. Typically result obtained by using this approach scales with the inverse of the visitation probability. However, here the results don't have this drawback.  
	
2. For the linear case, the paper considers the setting with an infinite set of states and the algorithm has access to the simulator of the dynamics of MDP. Then it provides the algorithm that obtains T^2/3 regret without assuming that the smallest eigenvalue of the covariance matrix \Sigma_h is at least \lambda_min and T^1/2 taken this assumption. The latter improves the previous result in the considered setting, which was T^2/3 regret, assuming that the smallest eigenvalue of \Sigma_h is bounded away from zero. The only drawback is that the algorithm is more computationally expensive since it requires O(T^H) number of calls to the simulator.
	
3. The third result presented in the paper is in the same setting as above but without access to the simulator of MDP, which is a very challenging setting. The obtained regret bound is T^6/7, and it makes use of the assumption on the smallest eigenvalue of \Sigma_h.

4. All three results from above make use of dilated bonuses, which is the main contribution of this paper. 
The use of the dilated bonuses that decrease the contribution to the regret, induced by the term appearing from the mismatch of q^*(x) and q(x), shows up in the analysis. To the best of my knowledge, this idea has not been considered before, and I think this idea is beneficial for future studies. 

main_review: 	
- The authors state that it is important to remove the use of an exploratory policy by the algorithm. Is there an argument why it is important and why it is better to be replaced by regularization of covariance matrix? Also, is there a technical reason why implicit exploration works better? 
	
-  Introducing the loss estimate for the tabular setting, it worth mentioning EXP3-IX algorithm for adversarial multi-armed bandits. 

- Would the dilated bonuses work the same way for the REPS approach?  

- Can the result of the Theorem 6.2 be improved by assuming that the comparator policy plays actions uniformly with some probability? 

limitations_and_societal_impact: There is no potential negative societal impact
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the regret of policy optimization for adversarial MDPs with bandit feedback. It develops a general solution that adds dilated bonuses to the policy update for exploration and applies the algorithm to the tabular, linear-Q, and linear MDP settings.   It shows that such a solution improves and generalizes the state-of-the-art.

main_review: - (+) For the tabular setting, the paper improved the regret analysis to $O(\sqrt{T})$ with dilated bonus. The idea is novel and the theoretical contribution is solid.

- (+) For the linear-Q setting, the paper establishes a regret of $O(T^{2/3})$ with the assumption on the existence of a simulator and $O(T^{1/2})$ with an exploratory policy. The assumptions are weaker than the previous work. The theoretical contribution of this part is solid.

- (+) The paper also provides regret for linear MDP without a simulator.

- (+) The mechanism of the dilated bonus is well discussed in Section 3.


- (-) The notation of $Q(x_h, a)$ and $V(x_h) $ are used without specification.  Such notations of value functions with specifying the timestep $h$ by subscription of $x$ is confusing. I suggest the authors to use e.g., $V(x, h)$ and $Q(x, a, h)$.


limitations_and_societal_impact: - The paper can include a table of the comparison of this work with previous works.

- The paper does not provide any empirical study to show that the dilated bonus works better. I understand this paper focuses on the theory but some toy examples could be helpful to show the benefit of the dilated bonus.
review_title: null

Meta-review: The paper proposes some interesting technical tools for online learning in MDPs with adversarial rewards, improving existing results in tabular MDPs and large-scale MDPs under realizable linear function approximation and bandit feedback. All reviewers appreciated the clear improvement over previous results and the novelty of the technical contribution, with some expert reviewers opining that the proposed techniques are likely to inspire future work in the field. Based on my own reading, I concur with this assessment and agree that the paper should definitely be accepted for publication at the conference.
Decision: Accept (Poster)