Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies risk-sensitive reinforcement learning. The objective is to maximize the worst $\alpha$-percent tail of the reward-to-go at each step. This paper designs algorithms for regret minimization and best policy identification problems using the concentration of conditional value at risk. For the regret minimization problem, regret upper and lower bounds are provided; for the best policy identification problem, the sample complexity upper and lower bounds are provided. This paper also studies the limiting case when $\alpha$ is close to 0, i.e.the worst path RL. 
strength_and_weaknesses: Strength:
1. The paper studies the CVaR-based MDPs with the unknown transition. 
2. Both upper and lower bounds results are provided.
3. The usage of concentration of conditional value at risk is interesting.

Weaknesses:
1. This paper does not use the Bernstein-type exploration bonuses. There could be potential improvements.
2. The lower bound results do not involve the size of state space, which seems loose.

I acknowledge the authors' response.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and comprehensive. The extension from the traditional RL framework to CVaR RL is interesting.
summary_of_the_review: This paper conducts a novel and comprehensive study for CVaR RL.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the RL problem with a CVAR objective, which concerns the tail of rewards instead of the expectation in standard RL. In the standard setting, the paper proposes two methods. The first method, named ICVaR-RM, focuses on regret minimization, and the paper also provides a matching lower bound. The second method, named ICVaR-BPI, focuses on returning an $\epsilon$-optimal policy. Finally, when the risk level $\alpha \to 0$, where the objective reduces to optimizing the worst-case cumulative reward, the authors propose MaxWP method that enjoys constant regret. 
strength_and_weaknesses: Strength:
1. I first find the technical results to be interesting. Especially the terms that have been singled out by the authors, e.g., the minimal visitation measure (Remark 1 in the paper). The authors have shown that this instance-dependent term not only appears in the regret upper bound, but also in the lower bound, demonstrating the importance of this term in CVaR RL problems.

2. I also appreciate the author's effort in interpreting the result after each main theorem, and the additional highlight in delineating the technical differences between solving the CVaR RL problems and standard RL problems. The proof overview is well-written and easy to follow.

Weakness:

There is one thing I recommend the authors to consider during revision. Namely, the value function and Q-function are defined in equations (i) and (ii), through recursion. Though I understand this might be concise and technically correct. This approach to some extent hides the true definition of the objective. Namely, how is it that this definition of value function reflects the goal of optimizing the tail? I find it hard to read the risk-averse nature of the problem simply from the DP equations. 

Minor Question:

1. Looking into the author's explanation on the constant-regret of Worst Path RL, I was wondering is the technical analysis fundamentally different in the Worst Path RL than the CVaR case (when $\alpha > 0$)?

clarity,_quality,_novelty_and_reproducibility: Quality: The results are interesting, new, and come with a clear presentation.

Clarity: The structure of the paper is well organized. Related works have been discussed sufficiently. The novel technical part of the results is also well explained. 

Originality: Both the results and the technical developments appear to be novel in the literature. 
summary_of_the_review: This paper studies the important problem of solving RL tasks with a risk-averse mindset. To this end, the authors propose new methods for solving CVaR RL problem, which performs efficient regret minimization (demonstrated by a matching upper and lower bound). The authors also additionally consider the limiting case, where the task is to optimize the worst-case cumulative reward, and a method with constant regret is proposed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a new risk-sensitive reinforcement learning formulation, namely iterated CVaR RL. It defines the value as the CVaR of the next step's value function with respect to the randomness in the states' transition. Under this framework, this paper proposes a regret minimization algorithm and a best policy identification algorithm, with regret and sample complexity upper bound respectively. The author also gives a lower bound of regret as well. Finally, this paper also studies the case of CVaR as the risk level $\alpha$ goes to zero, namely the worst path case, and gives a regret analysis. 
strength_and_weaknesses: Strength:
1. This paper proposed a new risk-sensitive RL formulation: iterated CVaR RL. Though the idea of iterated CVaR is not new, it is the first use case in RL to my knowledge. This paper gives a novel analysis and an alternative to standard CVaR MDP formulation.
2. The paper thoroughly discusses the theoretical results of iterated CVaR RL under different settings: risk minimization, the sample complexity of best policy identification, limitation case when \alpha goes to zero, and a lower bound for each case.

Weakness:
1. I think it could be better to have more discussion on the pros and cons of iterated CVaR RL with CVaR of return. With the current description in the main paper and comparison in Appendix C, it is not very convincing the iterated CVaR is more suitable for risk-sensitive RL than CVaR MDP. 
 - Iterated CVaR takes the alpha CVaR over each transition step. That means in an H-step problem, only the worst $\alpha^H$ portion of the outcome matter to this quantity. As it decreases exponentially, it's less convincing to me that such a quantity is a good metric to distinguish different algorithms. For a reasonable $H$, $1-\alpha^H$ portion could be more meaningful even for the risk-sensitive analysis since it could consider more catastrophic returns.
 - Based on the last point, it is more concerning that an action with better performance in the worst $\alpha^H$ portion could actually have worse performance in the rest (not only for overall performance but even under risk-sensitive metrics). An example could be constructed by considering different CDF curves of the full return.
2. The term $1/\min_{\pi,s, a} w(s, a)$ in Theorem 1 seems meaningless to me. It can be arbitrarily large in an MDP, as long as there exists one state such that it has zero probability to be visited by at least one action. This looks like a very weak condition so please correct me if I'm wrong. Otherwise, the bound only depends on $\alpha^H$ in almost all MDPs. The lower bound construction verified this, as the $min_{\pi,s, a} w(s, a) = \Theta(\alpha^H) $. If authors want to show that there is a real dependency on $min_{\pi,s, a} w(s, a)$, it needs to give a construction where $w$ terms can be changed freely without changing $\alpha$ or $H$. (Like the proof of regret lower bound on $S$ and $H$.)


Some minor writing issues and related work:
 - I didn't find a formal definition of $w_{\pi, h}(s, a)$ in Theorem 1. 
 - There exists work on efficient exploration with the CVaR of return (as CVaR MDP) in unknown MDP. E.g. Keramati et al., 2020, Being Optimistic to Be Conservative: Quickly Learning a CVaR Policy. 

clarity,_quality,_novelty_and_reproducibility: Clarity: The main paper is clear overall. It is not that easy to follow, but it's due to the nature of such a dense technical discussion. I think some discussions like comparison with CVaR MDP and Fei et al., should be mentioned in more detail in the main paper rather than the appendix, and some proof sketches can be deferred on the other hand. 

Quality: The technical results (upper bounds and lower bounds) are solid.

Novelty: It is the first work to introduce iterated CVaR to RL settings. The main techniques it used in the analysis follow the method in Zanette & Brunskill, 2019, and some adjustments to deal with the new challenges with iterated CVaR.

Reproducibility: Proof and code are included.

summary_of_the_review: This paper gives a new formulation of risk-sensitive RL, iterated CVaR. It's a different definition than most current work, which takes CVaR over the return variable. The analysis in this paper under iterated CVaR is thorough. The main concerns are about the significance of some technical results, and the comparison with the current CVaR MDP.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The work studies iterated CVaR RL, and its limiting case worst path RL, as a representative provably efficient risk-sensitive RL problem. Two metrics, namely regret and best policy identification, are proposed and provably efficient algorithms with nearly matching upperbounds are provided. 
strength_and_weaknesses: Strength
- The paper studies a setting that is novel and intriguing, offering new insights that are crucial to wider adoption of RL.
- The results obtained in the paper are comprehensive, covering both the best policy identification setting and the online learning setting.
- The regret decomposition used to obtain the main results is novel and not found in existing literature. 

Weakness
- Algorithmically the work is not sufficiently novel. The two proposed algorithms bear strong resemblance to their non-risk aware counterparts. Moreover, while the concentration analysis leverages novel decomposition techniques, the lemmas used to prove the results (e.g. Lemma D.1, which shows the concentration behavior of the empirical CVaR estimate) can be found in existing literature. Overall the proof structure still seems to largely follow the optimism principle in provably efficient reinforcement learning. It would be great if the authors could further elaborate on how their analysis is not a combination of existing techniques in RL and existing concentration results from CVaR literature.

------ Post response update --------

I have read the authors' response and my concerns are addressed.
clarity,_quality,_novelty_and_reproducibility: - Clarity. The paper is well-written and easy to follow.
- Quality. The claims made in the paper are correct and justified.
- Novelty. Please see the previous paragraph on novelty.
- Reproducible. The proofs and simulation results are reproducible.
summary_of_the_review: The paper studies an interesting problem, risk-sensitive RL, and provides comprehensive results. The analyses used to obtain these results feature novel techniques. While some aspects of the proof depend on existing work, to me it does not outweigh the contributions made by the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies a new risk-sensitive RL setting called Iterated CVaR RL, where the goal is to maximize the $\alpha$-tail of the value function for each (s,a) pair instead of the expectation as in standard RL or the $\alpha$-tail of the overall value function in CVaR RL. Nearly tight upper and lower bounds are provided for both regret minimization and best policy identification in the tabular MDP setting. 
There is a consensus among the reviewers that the paper is well-written and the technical contribution is solid. The authors have also provided an improved lower-bound construction in response to reviewer U4MP's comments. Overall, I believe this is a very solid paper and recommend acceptance.
justification_for_why_not_higher_score: The main reason for not oral/spotlight is that the studied problem is relatively niche and is an incrementally different setting than what is previously studied in risk-sensitive RL, i.e. CVaR RL.
justification_for_why_not_lower_score: The theoretical contribution is significant and there are new technical tools being develop that can be of independent interests.
Decision: Accept: poster