A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents

Dear Reviewer 74co,

Thank you for your encouraging review and strong support! We truly appreciate the time and effort that have been invested in providing constructive comments.

Regarding your question about notation on the value function:

• $\hat V_{1,k}$ is an estimated augmented value function from the Optimistic Oracle (Def 3.1). The subscript $1,k$ denotes it's at step $h=1$ and is from $k$-th round of the meta-algorithm (Alg 1).
• $V^{\pi^k}\_1$ and $V^{\pi^k}\_{\text{aug}}$ are both denoting the true augmented value function of policy $\pi^k$ at step $h=1$. Thanks for catching this duplicated notation, we will consolidate these two notations into one.

Regarding your concern about the novelty of our work: While the AugMDP has been studied for specific risk measures like CVaR, our work makes several novel contributions beyond straightforward application of this approach:

1. We establish the first risk-sensitive PAC bounds for exogenous block MDPs (Thm 3.6 in Sec 3.1) – not captured by low-rank MDPs (Zhao et al. 2024) and requires novel techniques to handle the interplay between coverability and the augmented MDP.
2. We derive the first risk-sensitive bounds for policy-gradient algorithms and prove a novel local improvement property in risk-sensitive RL (Thms 4.2 and 4.4 in Sec 4). This bridges the gap in the literature where policy gradient methods lacked theoretical guarantees in risk-sensitive settings.
3. By abstracting out oracles, we provide a unifying framework for studying the large class of OCE risk measures that were previously disconnected in the risk-sensitive RL literature (e.g., Bastani et al. 2022, Wang et al. 2023, Zhao et al. 2024). Our framework not only simplifies analysis but also enables new algorithmic design (leading to the above two contributions), applicable across multiple risk measures. Our Related Works section (Sec 1.1) provides a more comprehensive discussion that positions our novel contributions within the RL literature. We are happy to answer any questions on our technical contributions.

Please let us know if you have any other questions!

Dear Reviewer t1og,

Thanks very much for providing helpful feedback. We truly appreciate the time and effort that have been invested in providing constructive comments. Please find our responses below.

1. Our assumption to normalize cumulative rewards is actually more general than normalizing per-step reward, as it allows for reward values that drastically vary across actions and states. For example, the reward sequence $0, 0, ..., 0, H$ is allowed under our framework (after scaling our normalization & bounds by $H$). This is in contrast to assuming that per-step rewards are in $[0,1]$ and cumulative rewards are in $[0,H]$, the arguably more popular assumption in RL theory, which only allows for dense rewards and precludes the above sparse reward example. A helpful resource that helped us understand the benefit of normalizing cumulative rewards is the paper http://proceedings.mlr.press/v75/jiang18a/jiang18a.pdf (which we cite in line 145) and their COLT 2018 talk https://youtu.be/If63ZSpEiSs at the 5:10 mark.

2. We note that the AugMDP for OCE only has one extra dimensionality compared to the original MDP, since the augmented state $b_h$ is a scalar. Moreover, the AugMDP is very easy to simulate, since $b_h$ has a known and deterministic transition function $b_{h+1}=b_h-r_h$, which adds essentially no overhead to the original MDP. Please see "Remark: the AugMDP is easy to simulate" in Lines 184-191 for more details.

3. Thanks for the question. Regarding how to satisfy the two conditions (optimism and bounded regret) in Def 3.1, we note these conditions are satisfied by many optimistic algorithms in RL even when applied to the AugMDP. For example, UCB-VI satisfies these conditions in tabular MDPs, Rep-UCB in low-rank MDPs and GOLF in MDPs with exogenous block MDPs. We refer the reviewer to the paragraphs after Thm 3.2 and the text in 3.1 for several ways to satisfy these two conditions. Regarding logarithmic regret in the second condition, this is certainly captured by our framework; the second condition only states that regret should be sub-linear, which certainly includes $O(\log K)$ regret as well. The implication on the OCE convergence is stated in Thm 3.2, which shows that the OCE regret is bounded by the oracle's regret multiplied by a constant $V^{\max}_u$ that doesn't change the rate in $K$. Thus, an oracle with logarithmic regret would yield an OCE algorithm with logarithmic regret.

4. Thanks for the suggestion, we'll certainly add more intuition about $V^{\max}_u$: this constant intuitively captures is the statistical complexity of learning the OCE with utility $u$; for example, it is $1/\tau$ for CVaR at level $\tau$ and this is intuitive because smaller levels of $\tau$ measures a smaller sub-population and thus requires more samples to learn. We will list and discuss more examples of $V^{\max}_u$ in the main text (they are currently in Table 4 of the appendix due to page limit).

5. We will also elaborate more about the exogenous block MDP in the revision.

6. Thanks for the question. In theory, small value estimation error can be ensured by online supervised learning or regression, which is fairly standard (Agarwal et al. 2021). In practice, policy optimization algorithms such as REINFORCE with value baseline or PPO maintain a separate value network and interleave in gradient updates to the value network by minimizing squared loss (Schulman et al. 2017). We will add more discussions in the revision.

7. While we concur with the reviewer that our approaches are inspired by existing algorithms, we believe our work nonetheless contributes several novel and insightful results to risk-sensitive RL:

   1. We establish the first risk-sensitive PAC bounds for exogenous block MDPs (Thm 3.6 in Sec 3.1) – not captured by low-rank MDPs (Zhao et al. 2024) and requires novel techniques to handle the interplay between coverability and the augmented MDP.
   2. We derive the first risk-sensitive bounds for policy-gradient algorithms and prove a novel local improvement property in risk-sensitive RL (Thms 4.2 and 4.4 in Sec 4). This bridges the gap in the literature where policy gradient methods lacked theoretical guarantees in risk-sensitive settings.
   3. By abstracting out oracles, we provide a unifying framework for studying the large class of OCE risk measures that were previously disconnected in the risk-sensitive RL literature (e.g., Bastani et al. 2022, Wang et al. 2023, Zhao et al. 2024). Our framework not only simplifies analysis but also enables new algorithmic design (leading to the above two contributions), applicable across multiple risk measures. Our Related Works section (Sec 1.1) provides a more comprehensive discussion that positions our novel contributions within the RL literature. We are happy to answer any questions on our technical contributions.

Please let us know if you have any other questions!

Dear Reviewer ZPJ1,

Thanks very much for providing helpful feedback. We truly appreciate the time and effort that have been invested in providing constructive comments. Please find our responses below.

Reviewer: The empirical results are too minor to support the claim that the augmentation method is powerful.

Authors' reply: Yes, we concur that our empirical results are only a proof-of-concept, while our main contribution is theoretical. Our empirical simulation is specifically to show that, in a minimal MDP, our methods indeed learn the optimal risk-sensitive policy while previous algorithms with Markov policies have bounded performance (i.e. they fail to learn the optimal policy), which motivates further research to step away from Markov policies and to use the AugMDP.

Reviewer: My major concern is that the method in this work is very limited in both technical novelty and conceptual insight. Firstly, by the definition of OCE, it is very nature to formulate the problem with an augmented state space, which is roughly a combination of traditional RL (to learn $P$) with dynamic programming (to learn $b$). Secondly, the proofs in this work are merely straightforward applications of existing algorithms, which significantly limits the technical novelty.

Authors' reply: While we concur with the reviewer that our approaches are inspired by existing algorithms, we believe our work nonetheless contributes several novel and insightful results to risk-sensitive RL:

1. We establish the first risk-sensitive PAC bounds for exogenous block MDPs (Thm 3.6 in Sec 3.1) – not captured by low-rank MDPs (Zhao et al. 2024) and requires novel techniques to handle the interplay between coverability and the augmented MDP.
2. We derive the first risk-sensitive bounds for policy-gradient algorithms and prove a novel local improvement property in risk-sensitive RL (Thms 4.2 and 4.4 in Sec 4). This bridges the gap in the literature where policy gradient methods lacked theoretical guarantees in risk-sensitive settings.
3. By abstracting out oracles, we provide a unifying framework for studying the large class of OCE risk measures that were previously disconnected in the risk-sensitive RL literature (e.g., Bastani et al. 2022, Wang et al. 2023, Zhao et al. 2024). Our framework not only simplifies analysis but also enables new algorithmic design (leading to the above two contributions), applicable across multiple risk measures. Our Related Works section (Sec 1.1) provides a more comprehensive discussion that positions our novel contributions within the RL literature.

Reviewer: Why do you consider the assumption that $Z(\pi)\in[0,1]$, instead of the classical assumption that each $r_h\in[0,1]$?

Authors' reply: Our assumption to normalize cumulative rewards is actually more general than normalizing per-step reward as it allows for reward values that drastically vary across actions and states. For example, the reward sequence $0, 0, ..., 0, H$ is allowed under our framework (after scaling our normalization by $H$). This is in contrast to the arguably more popular assumption in the RL theory community that per-step rewards are in $[0,1]$ and cumulative rewards are in $[0,H]$, which only allows for dense rewards and precludes the above sparse reward example. A helpful resource that helped us understand the benefit of normalizing cumulative rewards is the paper http://proceedings.mlr.press/v75/jiang18a/jiang18a.pdf (which we cite at line 145) and their COLT 2018 talk https://youtu.be/If63ZSpEiSs at the 5:10 mark.

Please let us know if you have any other questions!

Dear Reviewer 5fhe,

Thanks for providing your helpful feedback. We truly appreciate the time and effort that have been invested in providing constructive comments. Please find our responses below.

Reviewer: The paper could benefit from more explanation. For example, in eq (1) defining OCE, it is unclear to me what this definition means. Some examples could help.

Authors' reply: Thanks for the suggestion. Eq (1) is the risk-sensitive RL objective defined using the static OCE risk measure and is the key objective we aim to optimize in the paper. Right after Eq (1), we provide a few examples of OCE risk measures, such as CVaR when u is the hinge utility and Markowitz's mean-variance when u is the quadratic utility. We will elaborate more on these examples in the revision by moving some content from Appendix B to the main text.

Reviewer: In def 3.1, an oracle is introduced. Is this oracle used in later algorithm designs? And how do you implement it?

Authors' reply: Thanks for the question! Yes, the optimistic oracle in Def 3.1 is used in the meta-algorithm Alg 1, and similarly the policy gradient oracle in Def 4.1 is used in the meta-algorithm Alg 2. In our paper, we discuss several examples of how to implement these oracles for different settings. For example, for the optimistic oracle in Def 3.1, we discuss three ways to implement it using (1) UCB-VI, (2) Rep-UCB and (3) GOLF. Moreover, for our policy gradient oracle in Def 4.1, we discuss natural policy gradients (NPG) as an example instantiation. By employing different oracles, we are able to derive guarantees in several types of MDPs, e.g. UCB-VI is used in tabular MDPs, Rep-UCB in low-rank MDPs, GOLF in exogenous block MDPs, NPG in MDPs with good initial state distribution, where the latter two are novel to risk-sensitive RL. If you have any further questions about how these oracles are implemented, we would be happy to answer them!

Dear Reviewer 1jGh,

Thanks very much for providing helpful feedback. We truly appreciate the time and effort that have been invested in providing constructive comments. Please find our responses below.

Reviewer: the constant $V^{\max}_u$ is not defined formally

Authors' reply: We kindly refer the reviewer to line 130 where $V^{\max}_u$ is defined. We will make sure to highlight this definition in the revision with examples and connection to Lipschitz risk measure (see next reply).

Reviewer: My main concern is that the author has not referenced the studies on the Lipschitz risk measure in [1, 2]. Although not previously discussed in related works, I believe that the OCE is encompassed within the Lipschitz risk measure. The factor $V^{\max}_u$ closely resembles the Lipschitz constant described in [1, 2], which might give a formal way to determine this factor. Since [2] has already proposed an optimism - based algorithm grounded in distribution learning for the Lipschitz risk, I suggest that the author offer a comprehensive comparison with [2]. This would help to clearly elucidate the novelty of the first contribution of this paper.

Authors' reply: Thanks very much for pointing out Lipschitz risk measures. You're right that they indeed encompass the OCE with Lipschitz constant at most $V^{\max}_u$ and we'll cite and discuss this as another way to interpret $V^{\max}_u$. Our work is distinguished from prior Lipschitz risk RL [1,2] as follows:

• [1] studies RL with dynamic risk objective (a.k.a. iterated risk) $\rho(r_1+\rho(r_2+\rho(r_3+...)))$ which measures per-step risk and is different from our static risk objective $\rho(r_1+r_2+r_3+...)$ which measures trajectory-wise risk. Both objectives are important and we discuss dynamic risks in Lines 110-128 of Related Works, to which we'll add a citation to [1].
• [2] derives regret bounds for static Lipschitz risks under function approximation which is more related to our setting. However, a key technical assumption made in [2] is bounded Bellman eluder dimension or witness rank, which are insufficient to capture the challenging exogenous block MDP setting. Indeed, the Bellman eluder dimension can grow with the size of the exogenous state space which is exponentially large or infinite (Xie et al. 2023). In contrast, we employ a coverability argument in the augmented MDP to obtain the first PAC bound for exogenous block MDP in risk-sensitive RL. Thus, our first contribution is distinct from [2] since our framework can deal with the challenging exogenous block MDP while [2] cannot. Moreover, our work includes other contributions such as studying policy gradient methods that are complementary to optimistic algorithms.

Reviewer: I recommend that the authors delve deeper into the computational efficiency of the proposed algorithms. For instance, they could explore and discuss what the major challenges are in developing a computationally and statistically efficient algorithm for OCE RL.

Authors' reply: Thanks for this suggestion, we'll certainly add more discussion in the revision. In short, our work shows that the computational and statistical complexity of OCE RL algorithms can largely be reduced to standard risk-neutral RL in the AugMDP. In terms of computation, the main costs come from 1) optimizing over $b$, which is efficient under reward discretization, and 2) querying the underlying risk-neutral RL oracle. In terms of sample efficiency, our main theorems (Thm 3.2 & 4.2) ensure that the OCE regret is bounded by the underlying oracle's regret up to constant factors. Thus, in both cases, the major challenge is devising a risk-neutral oracle that is efficient within the AugMDP. We will make sure to incorporate these discussions in the revision.

Reviewer: Given that discretizing the total reward in Risk-Sensitive Reinforcement Learning (RSRL) is a prevalent technique, as demonstrated in [3, 4], discretization appears to be a rational approach to address the discrete reward assumption (Assump. 3.5). Will this method works in OCE RL?

Authors' reply: Thanks for this question! Yes, discretizing rewards as in [3, 4] can indeed by used to address the discrete reward assumption (Assump 3.5), at the cost of a slower regret rate. Specifically, using a discretization width of $\epsilon$ introduces additional regret of $O(K\epsilon)$ and creates $|\mathcal{B}|=1/\epsilon$ atoms. Thus, our regret bound in Thm 3.6 would become $O(\sqrt{K/\epsilon} + K\epsilon)$. The $\epsilon$ which minimizes this is $\epsilon = \Theta(1/K^{1/3})$, which leads to a regret bound of $O(K^{2/3})$ which is sub-linear and meaningful. In other words, we can remove Assump 3.5 by discretizing rewards with bin width of $1/K^{1/3}$, and our regret bound in Thm 3.6 becomes $O(V^{\max}_uHK^{2/3} \sqrt{ Z^{en}A\log(|\mathcal{F}|/\delta) })$. We'll make sure to discuss this in the revision.

Please let us know if you have any other questions!