Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies the problem of risk-sensitive RL, and prove regret bound under a class of risk-sensitive objectives, including CVaR. The results build on a novel CVaR objective and optimistic MDP. 
strengths_and_weaknesses: Strengths
- The problem of risk-sensitive RL is interesting and important. 

Weaknesses
- The algorithmic part of the paper does not appear strong. 
- A better comparison with recent results would be helpful. 
questions: - It would be nice to provide some explanations to explicitly connect the formulation here with existing settings. 
- Also, while def. (1) appears to be more general, it would still help if the paper can discuss how it generalizes existing objectives. 
- The reviewer would suggest adding a thorough comparison with existing works. In particular, how are the dependence on different parameters compared to existing results? The paper only mentions the dependence on K. 
- The algorithmic aspect of the paper does not appear significant. In particular, the main results in the paper focus on showing equivalence or transformation. The proposed algorithm 1 does not appear to be novel (although this has nothing to do with its performance). The authors could perhaps better highlight the novelty of the results. 

limitations: - The algorithmic part of the paper does not appear strong. 
- A better comparison with recent results would be helpful.
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: This paper proposes an exploration learning algorithm for risk-sensitive reinforcement learning algorithm with provable guarantees on its performance using the metric of regret. 
strengths_and_weaknesses: Strengths: 

1. This paper presents a general approach for addressing the risk-sensitive reinforcement learning problems and use this approach to get provable regret guarantees. In particular, the paper considers the general formulation given Eq. (1). One of the most popular risk-sensitive criteria CVaR will become a special case of this formulation. 

2. According to this reviewer, the key contribution of this paper is the result given in Lemma 5.1. Risk-sensitive RL is difficult mainly because of the complicated form of the objective function. Lemma 5.1 converts this to a clearly tractably form, which can be used to bound the difference in the objective function due to two policies by the difference in quantile functions of the cumulative rewards induced by those policies. This result is possibly useful in many other research problems, including in the analysis of policy gradient algorithms. 

3. The paper also presents a new style of UCB algorithm which is different from the standard optimism in the face of uncertainty (OFU) algorithm. Most of the standard algorithms finds an optimistic model by searching within a ball around the empirical estimate of the model in such a way to maximize the objective. This paper seems to be directly selecting a model by subtracting a penalty term (corresponding to the visitation counts) from the estimated model. This will reduce the computational complexity compared to the standard OFU algorithm which requires approaches such as extended value iteration. 



Weaknesses:

1. Proofs are rather compressed. Please provide intuitive explanation general proof ideas. Also, please provide explanation for the intermediate steps. 
2. The motivation for using a different style of UCB approach is not clear. Is this approach used in prior works? What are the advantages or disadvantages of this approach? 
3. The computational feasibility of the proposed generalized form is not clear. Even for the CVaR setting, how is the oracle policy computed? For general setting, is there a standard algorithm? 
4. This reviewer acknowledges that this is a theoretical paper. However, given that it proposes a new algorithm, and deals only with tabular setting, it is important to include the experimental results which demonstrate the performance of the algorithm.  



questions: Please see "Weaknesses' above. 
limitations: Limitations are specified in the form of the assumptions.
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: This paper presented a novel regret bound analysis for risk-sensitive reinforcement learning. The analysis is based on an optimistic MDP formulation. The regret bound could be applied to more general problem formulations compared to existing regret bound analyses. Overall, I am not quite familiar with the related work of regret bounds of the risk-sensitive RL, and the authors also did not explain too much about related works in the main paper. Therefore, I am not sure if the claim of the first regret bound is right. However, the results are reasonable on CVaR problem formulation and seem plausible. Therefore, I have a positive impression of this paper. I also suggest that the author could explain more about related work (even though there might not be many) to help better understand this paper.
strengths_and_weaknesses: Strength:
The paper gave a thorough analysis of regret bound of risk-sensitive reinforcement learning. The notions are clear and the authors also explained many intuitions behind the proof.

Weakness:
The claim of the first regret bound might be too strong, and the logic of the whole paper could be further improved (e.g., there are many lemmas placed at the end that makes me confused initially. )
questions: 1. It seems that the results rely heavily on the Lipschitz constant $L_G$. What if the $L_G$ is not Lipschitz?
2. Are there any other requirements of the MDP, such as stationary or non-stationary?
limitations: The author adequately addressed the limitations and there is no potential social impact of this work.
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: 
This paper describes an optimistic algorithm for a general class of Risk-Sensitive RL, where the quantiles of the return distribution are weighted according to a function G.
The paper proves a regret-bound linear with respect to Lipschitz constant $L_G$ of the weight function.
strengths_and_weaknesses: 
### Strenghts

- The paper provides a novel analysis of a general class of Risk-sensitive RL problems.
- The paper is well written and well structured. The main results are proved in the main document and only the support material is left in the appendix.
- Overall, the paper provides an excellent presentation of the problem and the derivations.

### Weaknesses

- The motivation to study this general class of problems could be expanded to clarify further the significance of the proposed approach.
questions: 
- Between lines 113 and 114 should the left hand side of the equation be $\max_{\pi \in \Pi_{\text{Ind}}}\Phi_{\mathcal{\tilde{M}}}(\pi)$?
- In the right-hand side of the bottom equation after line 193, should it be $\epsilon_{R}^{(k)}$?
limitations: 
The paper clearly states the assumptions necessary to achieve the regret bounds claimed.
review_title: null

Meta-review: metareview: This paper proposes an optimistic algorithm for regret minimization of risk-sensitive measures in tabular episodic MDPs. It shows that this algorithm achieves a $\sqrt{S^3 A^2 K} L poly(T)$ regret bound where $K$ is the number of episodes,  $T$ is the episode length and $L$ is the Lipschitz-constant of the weighting function associated with the risk measure (e.g. CVaR). This is the first regret bound in this setting.

The initial assessment by all reviewers was overall positive. They appreciated this first result in this new and important setting. However, there were also concerns, especially regarding the algorithmic contribution and the comparison to related work. The authors' response could largely address these issues. However, there are still some concerns regarding the tightness of the analysis and the relation to techniques in existing work. These are described in detail below and have been discussed in the reviewers, AC and SAC discussion. 
All in all, the paper is recommended to be accepted because of its new guarantee in this new setting, motivating more research in this area that builds on this initial work. However, the authors are encouraged to further comment on the tightness of their analysis in the camera-ready version.

**Tightness of the Analysis**: The presented regret bound exhibits an additional $S \sqrt{A} L$ factor compared to state of the art regret bounds in the risk-neutral case. While a dependency on $L$ is expected in the risk-sensitive setting it is not clear that these additional $S$ and $A$ dependencies are necessary. The paper does not discuss where exactly these factors come from in the analysis and does not provide any regret lower bounds for this novel setting. While the rebuttal revision added a discussion to the paper on the existence of these additional factors compared to existing results for the risk-neutral case, several reviewers and the AC found this to be not quite satisfactory. The paper should discuss where these factors come from and why it would be difficult (if not impossible) to remove them.
Based on the AC's reading of the paper, these dependencies appear because of two places: (1) $\epsilon_P^{(k)}$ has a $\sqrt{S}$ dependency which seems to be derived from an $\ell_1$ concentration bound. However, it is not clear that this is really necessary and one could instead derive them from concentration arguments on individual $P(s'|s,a)$ probabilities since they are all down-shifted individually. (2) The final display in the proof of Thm 4.1 (Lines 475 and following) seemingly applies a standard argument in regret analyses but gets a worse dependency of S and A (linear instead of under the square root, compare for example to Eq 4.8 in https://arxiv.org/pdf/1807.03765.pdf). 
confidence: Certain
Decision: Accept