Burning RED: Unlocking Subtask-Driven Reinforcement Learning and Risk-Awareness in Average-Reward Markov Decision Processes

## Abstract

Abstract Average-reward Markov decision processes (MDPs) provide a foundational framework for sequential decision-making under uncertainty. However, average-reward MDPs have remained largely unexplored in reinforcement learning (RL) settings, with the majority of RL-based efforts having been allocated to episodic and discounted MDPs. In this work, we study a unique structural property of average-reward MDPs and utilize it to introduce Reward-Extended Differential (or RED ) reinforcement learning: a novel RL framework that can be used to effectively and efficiently solve various subtasks simultaneously in the average-reward setting. We introduce a family of RED learning algorithms for prediction and control, including proven-convergent algorithms for the tabular case. We then showcase the power of these algorithms by demonstrating how they can be used to learn a policy that optimizes, for the first time, the well-known conditional value-at-risk (CVaR) risk measure in a fully-online manner, without the use of an explicit bi-level optimization scheme or an augmented state-space.

## 1 Introduction

Markov decision processes (MDPs) [] are a long-established framework for sequential decision-making under uncertainty. Episodic and discounted MDPs, which aim to optimize a sum of rewards over time, have enjoyed success in recent years when utilizing reinforcement learning (RL) solution methods [] to tackle certain problems of interest in various domains. Despite this success however, these MDP-based methods have yet to be fully embraced in real-world applications due to the various intricacies and implications of real-world operation that often trump the ability of current state-of-the-art methods []. We therefore turn to the less-explored average-reward MDP, which aims to optimize the reward received per time-step, to see how its unique structural properties can be leveraged to tackle challenging problems that have evaded its episodic and discounted counterparts.

In particular, we focus our attention on one such problem where the average-reward MDP may offer structural advantages over episodic and discounted MDPs: risk-aware decision-making. More formally, a risk-aware (or risk-sensitive) MDP is an MDP which aims to optimize a risk-based measure instead of the typical (risk-neutral) expectation term. In this work, we show how leveraging the average-reward MDP allows us to overcome many of the computational challenges and non-trivialities that arise when performing risk-based optimization in episodic and discounted MDPs. In doing so, we arrive at a general-purpose, theoretically-sound framework that allows for a more subtask-driven approach to reinforcement learning, where various learning problems, or subtasks, are solved simultaneously to help solve a larger, central learning problem.

More formally, we introduce Reward-Extended Differential (or RED) reinforcement learning: a first-of-its-kind RL framework that makes it possible to effectively and efficiently solve various subtasks (or subgoals) simultaneously in the average-reward setting. At the heart of this framework is the novel concept of the reward-extended temporal-difference (TD) error, an extension of the celebrated TD error [], which we leverage in combination with a unique structural property of the average-reward MDP to solve various subtasks simultaneously. We first present the RED RL framework in a generalized way, then adopt it to successfully tackle a problem that has exceeded the capabilities of current state-of-the-art methods in risk-aware decision-making: learning a policy that optimizes the well-known conditional value-at-risk (CVaR) risk measure [] in a fully-online manner without the use of an explicit bi-level optimization scheme or an augmented state-space.

Our work is organized as follows: in Section 2 we provide a brief overview of relevant work done on average-reward RL as well as risk-aware learning and optimization in MDP-based settings. In Section 3 we give an overview of the fundamental concepts related to average-reward RL and CVaR. In Section 4 we introduce the RED RL framework, including the concept of the reward-extended TD error. We also introduce a family of RED RL algorithms for prediction and control, and highlight their convergence properties (with full convergence proofs in Appendix B). In Section 5 we illustrate, through numerical experiments, how RED RL can be used to successfully learn a policy that optimizes the CVaR risk measure. Finally, in Section 6 we emphasize our framework’s potential usefulness towards tackling other challenging problems outside the realm of risk-awareness, highlight some of its limitations, and suggest some directions for future research.

Summary of contributions: To the best of our knowledge: i) we present the first framework that leverages the average-reward MDP for solving various subtasks simultaneously; ii) we introduce the concept of the reward-extended TD error; iii) we provide the first control and prediction algorithms for solving various subtasks simultaneously in the average-reward setting, including proven-convergent algorithms for the tabular case; iv) we provide the first algorithm that optimizes CVaR in an MDP-based setting without the use of an explicit bi-level optimization scheme or an augmented state-space.

## 2 Related work

### 2.1 Average-reward reinforcement learning

Average-reward (or average-cost) MDPs were first studied in works such as []. Since then, there have been various, albeit limited, works that have explored average-reward MDPs in the context of RL (see [, ] for detailed literature reviews on average-reward RL). Recently, Wan et al. [] provided a rigorous theoretical treatment of average-reward MDPs in the context of RL, and proposed the proven-convergent ‘Differential Q-learning’ and (off-policy) ‘Differential TD-learning’ algorithms for the tabular case. Our work primarily builds off of Wan et al. [], and we utilize their proof technique when formulating the convergence proofs for our algorithms. To the best of our knowledge, our work is the first to explore solving subtasks simultaneously in the average-reward setting.

### 2.2 Risk-aware learning and optimization in MDPs

The notion of risk-aware learning and optimization in MDP-based settings has been long-studied, from the well-established expected utility framework [], to the more contemporary framework of coherent risk measures []. To date, these risk-based efforts have almost exclusively focused on the episodic and discounted settings. This includes notable works such as [] and [], which, similar to the work presented in this paper, aim to optimize the CVaR risk measure (see [, ] for detailed literature reviews). In the average-reward setting, [] recently proposed a set of algorithms for optimizing the CVaR risk measure, however their methods require the use of an augmented state-space and a sensitivity-based bi-level optimization. By contrast, our work, to the best of our knowledge, is the first to optimize the CVaR risk measure in an MDP-based setting without the use of an explicit bi-level optimization scheme or an augmented state-space.

## 3 Preliminaries

### 3.1 Average-reward reinforcement learning

A finite average-reward MDP is the tuple $\mathcal{M}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{R},p\rangle$, where $\mathcal{S}$ is a finite set of states, $\mathcal{A}$ is a finite set of actions, $\mathcal{R}\subset\mathbb{R}$ is a finite set of rewards, and $p:\mathcal{S}\,\times\,\mathcal{A}\,\times\,\mathcal{R}\,\times\,\mathcal{S}
\rightarrow{}[0,1]$ is a probabilistic transition function that describes the dynamics of the environment. At each discreet time step, $t=0,1,2,\ldots$, an agent chooses an action, $A_{t}\in\mathcal{A}$, based on its current state, $S_{t}\in\mathcal{S}$, and receives a reward, $R_{t+1}\in\mathcal{R}$, while transitioning to a (potentially) new state, $S_{t+1}$, such that $p(s^{\prime},r\mid s,a)=\mathbb{P}(S_{t+1}=s^{\prime},R_{t+1}=r\mid S_{t}=s,A_
{t}=a)$. In an average-reward MDP, the agent aims to find a policy, $\pi:\mathcal{S}\rightarrow{}\mathcal{A}$, that optimizes the long-run (or steady-state) average reward, $\bar{r}$, which is defined as follows (for a given policy $\pi$):

$$ $\bar{r}_{\pi}\doteq\lim_{n\rightarrow{}\infty}\frac{1}{n}\sum_{t=1}^{n}\mathbb {E}[R_{t}\mid S_{0},A_{0:t-1}\sim\pi].$ (1) $$

In this work, we limit our discussion to stationary Markov policies, which are time-independent policies that satisfy the Markov property. Now, in order to simplify Equation (1) into a more workable form, it is usually necessary to make certain assumptions about the Markov chain, $\{S_{t}\}$, induced by following policy $\pi$. This is in contrast to episodic and discounted MDPs, which are less reliant on the behavior of the underlying stochastic process. To this end, a unichain assumption is typically used when doing prediction (learning), and a communicating assumption is typically used when doing control (optimization). Such assumptions ensure that, for the induced Markov chain, a stationary (or steady-state) distribution of states, $\mu_{\pi}(s)\doteq\lim_{t\rightarrow{}\infty}\mathbb{P}(S_{t}=s\mid A_{0:t-1}
\sim\pi)$, exists and is independent of the initial state. This thereby guarantees the existence of an optimal average-reward (or reward-rate), $\bar{r}*$, and allows Equation (1) to be simplified to the following:

$$ $\bar{r}_{\pi}=\sum_{s\in\mathcal{S}}\mu_{\pi}(s)\sum_{a\in\mathcal{A}}\pi(a \mid s)\sum_{s^{\prime}\in\mathcal{S}}\sum_{r\in\mathcal{R}}p(s^{\prime},r\mid s ,a)r.$ (2) $$

The return of an MDP, $G_{t}$, captures how rewards are aggregated over the time horizon. In an average-reward MDP, the return is referred to as the differential return, and is defined as follows:

$$ $G_{t}\doteq R_{t+1}-\bar{r}_{\pi}+R_{t+2}-\bar{r}_{\pi}+R_{t+3}-\bar{r}_{\pi}+\ldots.$ (3) $$

As such, the Bellman equation for the state-value function, $v_{\pi}(s)\doteq\mathbb{E}_{\pi}[G_{t}\mid S_{t}=s]=\mathbb{E}[R_{t+1}-\bar{r}
_{\pi}+G_{t+1}\mid S_{t}=s]$, and the Bellman optimality equation for the state-action value function, $q_{\pi}(s,a)\doteq\mathbb{E}_{\pi}[G_{t}\mid S_{t}=s,A_{t}=a]$, for an average-reward MDP can be stated as follows (for a given policy $\pi$):

$$ $v_{\pi}(s)=\sum_{a}\pi(a\mid s)\sum_{s^{\prime}}\sum_{r}p(s^{\prime},r\mid s,a )[r-\bar{r}_{\pi}+v_{\pi}(s^{\prime})],$ (4) $$

$$ $q_{\pi}(s,a)=\sum_{s^{\prime}}\sum_{r}p(s^{\prime},r\mid s,a)[r-\bar{r}_{\pi}+ \max_{a^{\prime}}q_{\pi}(s^{\prime},a^{\prime})].$ (5) $$

These equations can then be used in conjunction with solution methods (dynamic programming or RL) to find a policy that yields the optimal long-run average-reward. Note that solution methods typically find solutions to Equations (4) and (5) up to a constant, $c$. This is typically not a concern, given that the relative ordering of policies is usually what is of interest.

The underlying process by which average-reward MDPs operate is depicted in Fig. 1, where a given policy, $\pi$, induces a Markov chain, $\{S_{t}\}_{\pi}$, that yields a stationary reward distribution, whose mean corresponds to the long-run average-reward $\bar{r}_{\pi}$. Different policies can then be compared based on their $\bar{r}_{\pi}$ values to find the policy that yields the optimal average-reward.

In the context of RL, Wan et al. [] proposed the tabular ‘Differential TD-learning’ and ‘Differential Q-learning’ algorithms, which approximate the state-value and state-action value functions as follows:

$$ $\displaystyle V_{t+1}(S_{t})\doteq V_{t}(S_{t})+\alpha_{t}\rho_{t}\delta_{t}$ (6a) $\displaystyle V_{t+1}(s)\doteq V_{t}(s),\quad\forall s\neq S_{t}$ (6b) $\displaystyle\delta_{t}\doteq R_{t+1}-\bar{R}_{t}+V_{t}(S_{t+1})-V_{t}(S_{t})$ (6c) $\displaystyle\bar{R}_{t+1}\doteq\bar{R}_{t}+\eta\alpha_{t}\rho_{t}\delta_{t}$ (6d) $$

$$ $\displaystyle Q_{t+1}(S_{t},A_{t})\doteq Q_{t}(S_{t},A_{t})+\alpha_{t}\delta_{t}$ (7a) $\displaystyle Q_{t+1}(s,a)\doteq Q_{t}(s,a),\quad\forall s,a\neq S_{t},A_{t}$ (7b) $\displaystyle\delta_{t}\doteq R_{t+1}-\bar{R}_{t}+\max_{a}Q_{t}(S_{t+1},a)-Q_{ t}(S_{t},A_{t})$ (7c) $\displaystyle\bar{R}_{t+1}\doteq\bar{R}_{t}+\eta\alpha_{t}\delta_{t}$ (7d) $$

where, $\alpha_{t}$ is the step size, $\delta_{t}$ is the TD error, $\rho_{t}\doteq\pi(A_{t}\mid S_{t})\,/\,B(A_{t}\mid S_{t})$ is the importance sampling ratio (with behavior policy $B$), $\bar{R}_{t}$ is an estimate of the average-reward, $\bar{r}_{\pi}$, and $\eta$ is a positive scalar.

Figure: Figure 1: Visual depiction of the underlying process by which average-reward MDPs operate. Here, following policy $\pi$ induces a Markov chain, ${\{S_{t}\}}_{\pi}$. As $t\to\infty$, this yields a stationary (or steady-state) reward distribution with an average reward, $\bar{r}_{\pi}$. It is this long-run (or steady-state) average-reward that the standard average-reward MDP formulation aims to optimize.
Refer to caption: extracted/5965996/images/average_reward.png

### 3.2 Conditional value-at-risk (CVaR)

Consider a random variable $X$ with a finite mean on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, and with a cumulative distribution function $F(x)=\mathbb{P}(X\leq x)$. The (left-tail) value-at-risk (VaR) of $X$ with parameter $\tau\in(0,1)$ represents the $\tau$-quantile of $X$, such that $\text{VaR}_{\tau}(X)=\max\{x\mid F(x)\leq\tau\}$. The (left-tail) conditional value-at-risk (CVaR) of $X$ with parameter $\tau$ is defined as follows:

$$ $\text{CVaR}_{\tau}(X)=\frac{1}{\tau}\int_{0}^{\tau}\text{VaR}_{u}(X)du.$ (8) $$

When $F(X)$ is continuous at $x=\text{VaR}_{\tau}(X)$, the conditional value-at-risk can be written as follows:

$$ $\text{CVaR}_{\tau}(X)=\mathbb{E}[X\mid X\leq\text{VaR}_{\tau}(X)].$ (9) $$

Hence, Equation (9) allows for the interpretation of CVaR as the expected value of the $\tau$ left quantile of the distribution of $X$. Fig. 2a) depicts this interpretation of CVaR. In this work, we aim to optimize the CVaR of the stationary reward distribution. Fig. 2b) compares the CVaR of two stationary reward distributions that have the same long-run average-reward. In recent years, CVaR has emerged as a popular risk measure, in-part because it is a ‘coherent’ risk measure [], meaning that it satisfies key mathematical properties which can be meaningful in safety-critical and risk-related applications.

Figure: Figure 2: a) The left-tail conditional value-at-risk (CVaR) of a probability distribution; b) The stationary reward distributions induced by two policies, $\pi_{1}$ and $\pi_{2}$. Both distributions have the same long-run average-reward, but different CVaR values.
Refer to caption: extracted/5965996/images/cvar_full.png

An important, well-known property of CVaR, which we will use in our analysis, is that it can be represented as follows []:

$$ $\text{CVaR}_{\tau}(X)=\max_{b\in\mathbb{R}}\mathbb{E}[b-\frac{1}{\tau}(b-X)^{+ }]=\mathbb{E}[\text{VaR}_{\tau}(X)-\frac{1}{\tau}(\text{VaR}_{\tau}(X)-X)^{+}],$ (10) $$

where, $(y)^{+}=\max(y,0)$. Existing methods typically formulate the CVaR optimization problem as the following bi-level optimization with an augmented state-space that includes an estimate of $\text{VaR}_{\tau}(X)$ (in this case, $b$):

$$ $\max_{\pi}\text{CVaR}_{\tau}(X)=\max_{\pi}\max_{b\in\mathbb{R}}\mathbb{E}[b- \frac{1}{\tau}(b-X)^{+}]=\max_{b\in\mathbb{R}}(b-\frac{1}{\tau}\max_{\pi} \mathbb{E}[(b-X)^{+}]),$ (11) $$

where the ‘inner’ optimization problem can be solved using standard MDP solution methods.

## 4 Reward-extended differential (RED) reinforcement learning

We now present our primary contribution: a framework for solving various subtasks simultaneously in the average-reward setting. We call this framework reward-extended differential (or RED) reinforcement learning. The ‘differential’ part of the name comes from the use of the differential algorithms from average-reward MDPs. The ‘reward-extended’ part of the name comes from the use of the reward-extended TD error, a novel concept that we will introduce shortly. We will show how combining the reward-extended TD error with a unique structural property of average-reward MDPs allows us to solve various subtasks simultaneously in an effective and efficient manner. We first derive the overall framework, then present a family of RL algorithms that utilize the framework. In the subsequent section, we will utilize this framework to tackle the CVaR optimization problem.

### 4.1 The framework

We begin our discussion by first describing what is meant by a ‘subtask’. Consider our goal of finding a policy that induces a stationary reward distribution with an optimal reward CVaR. We can see from Equation (10) that the reward CVaR can be interpreted as an expectation (or average) of sorts, which suggests that it may be possible to leverage the average-reward MDP to optimize this expectation, by treating the reward CVaR as the $\bar{r}_{\pi}$ that we want to optimize. However, this requires that we know the optimal value of the scalar $b$, because the aforementioned expectation only holds for this optimal value (which corresponds to the reward VaR, as per Equation (10)). Unfortunately, this optimal value is typically not known beforehand, so in order to optimize CVaR, we also need to optimize $b$. In this scenario, $b$ is the subtask that we are interested in solving because if we optimize $b$, in addition to CVaR, we will have our desired optimal solution. More generally, we can define a subtask as follows:

###### Definition 4.1 (Subtask) .

A subtask, $z_{i}$, is any scalar prediction or control objective belonging to a corresponding finite set $\mathcal{Z}_{i}\subset\mathbb{R}$, such that:

i) there exists a linear (or piecewise linear) function, $f:\mathcal{R}\,\times\,\mathcal{Z}_{1}\,\times\,\mathcal{Z}_{2}\,\times\,
\cdots\,\times\,\mathcal{Z}_{i}\,\times\,\cdots\,\times\,\mathcal{Z}_{n}
\rightarrow\tilde{\mathcal{R}}$, that is invertible with respect to each input given all other inputs, where $\mathcal{R}$ is the finite set of observed per-step rewards from the MDP $\mathcal{M}$, $\mathcal{\tilde{R}}\subset\mathbb{R}$ is a modified, finite set of per-step rewards whose long-run average is the primary prediction or control objective of the modified MDP, $\mathcal{\tilde{M}}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{\tilde{R}},p\rangle$, and $\mathcal{Z}=\{z_{1}\in\mathcal{Z}_{1},z_{2}\in\mathcal{Z}_{2},\ldots,z_{n}\in
\mathcal{Z}_{n}\}$ is the set of $n$ subtasks that we wish to solve; and

ii) $z_{i}$ is independent of the states and actions, and hence independent of the observed per-step reward, $r\in\mathcal{R}$, such that $\mathbb{E}[f(r,z_{1},z_{2},\ldots,z_{n})]=f(\mathbb{E}[r],z_{1},z_{2},\ldots,z
_{n})$.

With this definition in mind, we now proceed by providing the basic intuition behind our framework by using the average-reward itself, $\bar{r}_{\pi}$, as a blueprint of sorts for how we will derive the update rules in our learning algorithms for our subtasks. In particular, we will show how the process for deriving the update rule for the average-reward estimate, $\bar{R}_{t}$, in Equations (6) and (7) can be adapted to derive equivalent update rules for estimates corresponding to any subtask that satisfies Definition 4.1.

Consider the Bellman equation (4). We begin by pointing out that the average-reward satisfies many of the key properties of a subtask. In particular, we can see that $\bar{r}_{\pi}$ satisfies $\mathbb{E}[r-\bar{r}_{\pi}+v_{\pi}(s^{\prime})]=\mathbb{E}[r+v_{\pi}(s^{\prime
})]-\bar{r}_{\pi}$. This allows us to rewrite the Bellman equation (4) as follows:

$$ $\bar{r}_{\pi}=\sum_{a}\pi(a\mid s)\sum_{s^{\prime},r}p(s^{\prime},r\mid s,a)[r +v_{\pi}(s^{\prime})-v_{\pi}(s)].$ (12) $$

Now, if we wanted to learn $\bar{r}_{\pi}$ from experience, we can utilize the common RL update rule of the form: NewEstimate $\leftarrow$ OldEstimate $+$ StepSize [Target $-$ OldEstimate] [] to do so. In this case, the ‘target’ is the term inside the expectation in Equation (12). This yields the update in Equation (6d): $\bar{R}_{t+1}=\bar{R}_{t}+\eta\alpha\delta_{t}$. Hence, we are able to learn $\bar{r}_{\pi}$ using the TD error, $\delta$. This highlights a unique structural property of average-reward MDPs: we are able to simultaneously predict (learn) the value function and the average-reward using the TD error. Similarly, in the control case we are able to simultaneously control (optimize) these same two objectives using the TD error.

We will now show, through the RED RL framework, how this structural property can be utilized to simultaneously predict or control any subtask that satisfies Definition 4.1. More specifically, we will show how we can replicate what we just did for the average-reward for any arbitrary subtask:

###### Theorem 4.1 (The RED Theorem) .

An average-reward MDP can simultaneously predict or control any arbitrary number of subtasks using the TD error.

###### Proof.

Let $\tilde{r}=f(r,z_{1},z_{2},\ldots,z_{n})=f(\cdot)$ be a valid subtask function (as per Definition 4.1) corresponding to $n$ subtasks, where $r\in\mathcal{R}$ is the observed per-step reward, and $\tilde{r}\in\mathcal{\tilde{R}}$ is the modified per-step reward whose long-run average, $\bar{r}_{\pi}$, is the primary prediction or control objective.

First consider the TD error for the prediction case: $\delta=\tilde{r}-\bar{r}_{\pi}+v_{\pi}(s^{\prime})-v_{\pi}(s)=f(r,z_{1},z_{2},
\ldots,z_{n})-\bar{r}_{\pi}+v_{\pi}(s^{\prime})-v_{\pi}(s)$. Because the TD error is a linear function of $\tilde{r}=f(\cdot)$, and because $f(\cdot)$ itself is linear and satisfies $\mathbb{E}[f(r,z_{1},\ldots,z_{n})]=f(\mathbb{E}[r],z_{1},\ldots,z_{n})$, we have, by linearity of expectation:

$$ $\displaystyle\mathbb{E}[\delta]$ $\displaystyle=\mathbb{E}[f(r,z_{1},z_{2},\ldots,z_{n})-\bar{r}_{\pi}+v_{\pi}(s ^{\prime})-v_{\pi}(s)]$ (13a) $\displaystyle=f(\mathbb{E}[r-\bar{r}_{\pi}+v_{\pi}(s^{\prime})-v_{\pi}(s)],z_{ 1},\ldots,z_{n}).$ (13b) $$

Now consider an arbitrary subtask, $z_{i}\in\mathcal{Z}_{i}$, in Equation (13b). Since $f(\cdot)$ is linear and invertible with respect to each input given all other inputs, we can write $z_{i}$ as follows:

$$ $\displaystyle z_{i}$ $\displaystyle=f^{-1}(\mathbb{E}[\delta]\mid\mathbb{E}[r-\bar{r}_{\pi}+v_{\pi}( s^{\prime})-v_{\pi}(s)],z_{1},\ldots,z_{i-1},z_{i+1},\ldots,z_{n}))$ (14a) $\displaystyle z_{i}$ $\displaystyle=\mathbb{E}[f^{-1}(\delta\mid r-\bar{r}_{\pi}+v_{\pi}(s^{\prime}) -v_{\pi}(s),z_{1},\ldots,z_{i-1},z_{i+1},\ldots,z_{n})]$ (14b) $\displaystyle\doteq\mathbb{E}[f^{-1}_{i}(\delta)],$ (14c) $$

where $f^{-1}_{i}(\delta)$ denotes the inverse of the TD error with respect to $z_{i}$ given all other inputs.

Now, let $g_{z_{i}}$ denote $f^{-1}_{i}(\delta)$ when $\delta=0$, such that $g_{z_{i}}\doteq f^{-1}_{i}(0)$. With this notation in mind, and denoting the expectation, $\mathbb{E}$, as shorthand for the sums in the Bellman equation (4), we can rewrite the Bellman equation (4) for the MDP $\mathcal{\tilde{M}}$ and solve for $z_{i}$ as follows:

$$ $\displaystyle v_{\pi}(s)$ $\displaystyle=\mathbb{E}[f(r,z_{1},z_{2},\ldots,z_{n})-\bar{r}_{\pi}+v_{\pi}(s ^{\prime})]$ (15a) $\displaystyle 0$ $\displaystyle=\mathbb{E}[f(r,z_{1},z_{2},\ldots,z_{n})-\bar{r}_{\pi}+v_{\pi}(s ^{\prime})-v_{\pi}(s)]$ (15b) $\displaystyle 0$ $\displaystyle=f\left(\mathbb{E}[r-\bar{r}_{\pi}+v_{\pi}(s^{\prime})-v_{\pi}(s) ],z_{1},z_{2},\ldots,z_{n}\right)$ (15c) $\displaystyle z_{i}$ $\displaystyle=\mathbb{E}[f^{-1}_{i}(0)]$ (15d) $\displaystyle z_{i}$ $\displaystyle=\mathbb{E}[g_{z_{i}}].$ (15e) $$

Thus, to learn $z_{i}$ from experience, we can utilize the common RL update rule (in a similar fashion to what we did with Equation (12) for the average-reward), which yields the update:

$$ $\displaystyle Z_{i,t+1}$ $\displaystyle=Z_{i,t}+\eta\alpha[g_{{z_{i}},t}-Z_{i,t}]$ (16a) $\displaystyle\doteq Z_{i,t}+\eta\alpha\beta_{i,t},$ (16b) $$

where $Z_{i,t}$ is the estimate of subtask $z_{i}$ at time $t$, and $\eta\alpha$ is the step size.

Here, we define $\beta_{i}$ as the reward-extended TD error for subtask $z_{i}$. Our rationale for the naming of the reward-extended TD error stems from the fact that this term satisfies a TD error-dependent property: it goes to zero as the TD error, $\delta$, goes to zero. This follows from Equation (15e), where $g_{z_{i}}=z_{i}$ when $\delta=0$, which consequently zeroes out the reward-extended TD error in Equation (16). This implies that, like the average-reward update in Equation (6d), the arbitrary subtask update is dependent on the TD error, such that the subtask estimate will only cease to update once the TD error is zero. Hence, minimizing the TD error allows us to solve the arbitrary subtask simultaneously. This relationship between the reward-extended TD error and the regular TD error is formalized in Corollary 4.1 below. In Section 5, we will see that this property allows us to write the reward-extended TD error update as some constant, subtask-specific fraction of the regular TD error update.

###### Corollary 4.1 .

Let $\beta_{i,t}$ denote the reward-extended TD error for subtask $z_{i}$, and $\delta_{t}$ denote the regular TD error at time $t$. Then, $\beta_{i,t}=0$ if $\delta_{t}=0$.

###### Proof.

Consider the definition of the reward-extended TD error, $\beta_{i,t}\doteq g_{{z_{i}},t}-Z_{i,t}$. By Equation (15), when $\delta_{t}=0$, then $g_{{z_{i}},t}=Z_{i,t}$. As such, $\beta_{i,t}=0$ when $\delta_{t}=0$.
∎

As such, we have derived an update rule based on the TD error for our arbitrary subtask, $z_{i}$. Finally, because we picked $z_{i}$ arbitrarily, it follows that we can derive an update rule for every subtask in $f(\cdot)$ based on the TD error. This means that we can perform prediction for all our subtasks simultaneously by minimizing the (regular) TD error. The same logic can be applied in the control case to derive equivalent updates, where we note that it directly follows from Definition 4.1 that the existence of an optimal average-reward, $\bar{r}*$, implies the existence of corresponding optimal subtask values, $z_{i}^{*}\;\forall z_{i}\in\mathcal{Z}$. This completes the proof of Theorem 4.1.
∎

###### Definition 4.1 (Subtask) .

###### Theorem 4.1 (The RED Theorem) .

###### Proof.

###### Corollary 4.1 .

###### Proof.

### 4.2 The algorithms

We now present our family of RED RL algorithms. The full set of algorithms, including algorithms that utilize function approximation, are included in Appendix A. We provide full convergence proofs for the tabular algorithms in Appendix B.

RED TD-learning algorithm (tabular): We update a table of estimates, $V_{t}:\mathcal{S}\rightarrow\mathbb{R}$ as follows:

$$ $\displaystyle\tilde{R}_{t+1}=f(R_{t+1},Z_{1,t},Z_{2,t},\ldots,Z_{n,t})$ (17a) $\displaystyle\delta_{t}=\tilde{R}_{t+1}-\bar{R}_{t}+V_{t}(S_{t+1})-V_{t}(S_{t})$ (17b) $\displaystyle V_{t+1}(S_{t})=V_{t}(S_{t})+\alpha_{t}\rho_{t}\delta_{t}$ (17c) $\displaystyle V_{t+1}(s)=V_{t}(s),\quad\forall s\neq S_{t}$ (17d) $\displaystyle\bar{R}_{t+1}=\bar{R}_{t}+\eta_{r}\alpha_{t}\rho_{t}\delta_{t}$ (17e) $\displaystyle Z_{i,t+1}=Z_{i,t}+\eta_{z_{i}}\alpha_{t}\rho_{t}\beta_{i,t}, \quad\forall z_{i}\in\mathcal{Z}$ (17f) $$

where, $R_{t}$ is the observed reward, $Z_{i,t}$ is an estimate of subtask $z_{i}$, $\beta_{i,t}$ is the reward-extended TD error for subtask $z_{i}$, $\alpha_{t}$ is the step size, $\delta_{t}$ is the TD error, $\rho_{t}$ is the importance sampling ratio, $\bar{R}_{t}$ is an estimate of the long-run average-reward of $\tilde{R}_{t}$, $\bar{r}_{\pi}$, and $\eta_{r},\eta_{z_{i}}$ are positive scalars. Wan et al. [] showed for their Differential TD-learning algorithm that $R_{t}$ converges to $\bar{r}_{\pi}$, and $V_{t}$ converges to a solution of $v$ in Equation (4) for a given policy $\pi$. We now provide an equivalent theorem for our RED TD-learning algorithm, which also shows that $Z_{i,t}$ converges to $z_{i,{\pi}}\;\forall z_{i}\in\mathcal{Z}$, where $z_{i,{\pi}}$ denotes the subtask value when following policy $\pi$:

###### Theorem 4.2 (informal) .

The RED TD-learning algorithm (17) converges, almost surely, $\bar{R}_{t}$ to $\bar{r}_{\pi}$, $Z_{i,t}$ to $z_{i,{\pi}}\;\forall z_{i}\in\mathcal{Z}$, and $V_{t}$ to a solution of $v$ in the Bellman Equation (4), if the following assumptions hold: 1) the Markov chain induced by the target policy $\pi$ is unichain, 2) every state–action pair for which $\pi(a\mid s)>0$ occurs an infinite number of times under the behavior policy, 3) the step sizes are decreased appropriately, 4) the ratio of the update frequency of the most-updated state to the least-updated state is finite, and 5) the subtasks are in accordance with Definition 4.1.

###### Proof.

See Appendix B for the full proof.
∎

RED Q-learning algorithm (tabular): We update a table of estimates, $Q_{t}:\mathcal{S}\,\times\,\mathcal{A}\rightarrow\mathbb{R}$ as follows:

$$ $\displaystyle\tilde{R}_{t+1}=f(R_{t+1},Z_{1,t},Z_{2,t},\ldots,Z_{n,t})$ (18a) $\displaystyle\delta_{t}=\tilde{R}_{t+1}-\bar{R}_{t}+\max_{a}Q_{t}(S_{t+1},a)-Q _{t}(S_{t},A_{t})$ (18b) $\displaystyle Q_{t+1}(S_{t},A_{t})=Q_{t}(S_{t},A_{t})+\alpha_{t}\delta_{t}$ (18c) $\displaystyle Q_{t+1}(s,a)=Q_{t}(s,a),\quad\forall s,a\neq S_{t},A_{t}$ (18d) $\displaystyle\bar{R}_{t+1}=\bar{R}_{t}+\eta_{r}\alpha_{t}\delta_{t}$ (18e) $\displaystyle Z_{i,t+1}=Z_{i,t}+\eta_{z_{i}}\alpha_{t}\beta_{i,t},\quad\forall z _{i}\in\mathcal{Z}$ (18f) $$

where, $R_{t}$ is the observed reward, $Z_{i,t}$ is an estimate of subtask $z_{i}$, $\beta_{i,t}$ is the reward-extended TD error for subtask $z_{i}$, $\alpha_{t}$ is the step size, $\delta_{t}$ is the TD error, $\bar{R}_{t}$ is an estimate of the long-run average-reward of $\tilde{R}_{t}$, $\bar{r}_{\pi}$, and $\eta_{r},\eta_{z_{i}}$ are positive scalars. Wan et al. [] showed for their Differential Q-learning algorithm that $R_{t}$ converges to $\bar{r}*$, and $Q_{t}$ converges to a solution of $q$ in Equation (5). We now provide an equivalent theorem for our RED Q-learning algorithm, which also shows that $Z_{i,t}$ converges to the corresponding optimal subtask value $z_{i}^{*}\;\forall z_{i}\in\mathcal{Z}$:

###### Theorem 4.3 (informal) .

The RED Q-learning algorithm (18) converges, almost surely, $\bar{R}_{t}$ to $\bar{r}*$, $Z_{i,t}$ to $z_{i}^{*}\;\forall z_{i}\in\mathcal{Z}$, $Q_{t}$ to a solution of $q$ in the Bellman Equation (5), $\bar{r}_{\pi_{t}}$ to $\bar{r}*$, and $z_{i,{\pi_{t}}}$ to $z_{i}^{*}\;\forall z_{i}\in\mathcal{Z}$, for all $s\in\mathcal{S}$, where $\pi_{t}$ is any greedy policy with respect to $Q_{t}$, if the following assumptions hold: 1) the MDP is communicating, 2) the solution of $q$ in 5 is unique up to a constant, 3) the step sizes are decreased appropriately, 4) all the state–action pairs are updated an infinite number of times, 5) the ratio of the update frequency of the most-updated state–action pair to the least-updated state–action pair is finite, and 6) the subtasks are in accordance with Definition 4.1.

###### Proof.

See Appendix B for the full proof.
∎

###### Theorem 4.2 (informal) .

###### Proof.

###### Theorem 4.3 (informal) .

###### Proof.

## 5 Case study: RED RL for CVaR optimization

We now illustrate the usefulness of the RED RL framework by showing how it can be used to learn a policy that optimizes the CVaR risk measure without the use of an explicit bi-level optimization scheme (as in Equation (11)), or an augmented state-space.

As mentioned in Section 4.1, our goal is to learn a policy that induces a stationary reward distribution with an optimal reward CVaR (instead of the regular average-reward). Here, the reward CVaR is our primary control objective (i.e., the $\bar{r}_{\pi}$ that we want to optimize), and the reward VaR ($b$ in Equation (10)) is our subtask. When we apply the RED RL framework, using a modified version of Equation (10) as the subtask function (see Appendix C for more details), we arrive at the RED CVaR algorithms (see Appendix C for the full algorithms), which have the following update for our subtask, VaR:

$$ $\text{VaR}_{t+1}=\begin{cases}\text{VaR}_{t}-\eta\alpha\delta_{t},&R_{t}\geq \text{VaR}_{t}\\ \text{VaR}_{t}+\eta\alpha(\frac{\tau}{1-\tau})\delta_{t}&R_{t}<\text{VaR}_{t} \end{cases}\,,$ (19) $$

where $\eta\alpha$ is the step size, $\tau$ is the CVaR parameter, and $\delta_{t}$ is the regular TD error. As such, we can see that a subtask update, which utilizes the reward-extended TD error, ultimately amounts to an ‘extended’ version of the regular TD update. Consequently, this update rule allows us to optimize our subtask, VaR, without the use of an explicit bi-level optimization scheme or an augmented state-space.

We now present empirical results when applying the RED CVaR algorithms on two learning tasks. The first task is a two-state environment that we created for the purposes of testing our algorithms. It is called the red-pill blue-pill environment (see Appendix D), where at every time step an agent can take either a red pill, which takes them to the ‘red world’ state, or a blue pill, which takes them to the ‘blue world’ state. Each state has its own characteristic reward distribution, and in this case, the red world state has a reward distribution with a lower (worse) mean but higher (better) CVaR compared to the blue world state. Hence, we would expect the regular Differential Q-learning algorithm to learn a policy that prefers to stay in the blue world, and that the RED CVaR Q-learning algorithm learns a policy that prefers to stay in the red world. This task is illustrated in Fig. 3a).

The second learning task is the well-known inverted pendulum task, where an agent learns how to optimally balance an inverted pendulum. We chose this task because it provides us with opportunity to test our algorithm in an environment where: 1) we must use function approximation (given the large state and action spaces), and 2) where the policy for the optimal average-reward and the policy for the optimal reward CVaR is the same policy (i.e., the policy that best balances the pendulum will yield a stationary reward distribution with both the optimal average-reward and reward CVaR). This hence allows us to directly compare the performance of our RED algorithms to the regular Differential learning algorithms, as well as to gauge how function approximation affects the performance of our algorithms. For this task, we utilized a simple actor-critic architecture [] as this allowed us to compare the performance of the (non-tabular) RED TD-learning algorithm with a (non-tabular) Differential TD-learning algorithm. This task is illustrated in Fig. 3b). The full set of experimental details, including the full algorithms used, can be found in Appendix C.

Figure: Figure 3: An illustration of the a) red-pill blue-pill, and b) inverted pendulum environments.
Refer to caption: extracted/5965996/images/experiments.png

In terms of empirical results, Fig. 4 shows rolling averages of the average-reward and reward CVaR as learning progresses in both tasks when using the regular Differential learning algorithms (to optimize the average-reward) vs. the RED CVaR learning algorithms (to optimize the reward CVaR). As shown in the figure, in the red-pill blue-pill task the RED CVaR algorithm is able to successfully learn a policy that prioritizes maximizing the reward CVaR over the average-reward, thereby achieving a sort of risk-awareness. In the inverted pendulum task, both methods converge to the same policy, as expected. Fig. 5 shows typical convergence plots of the agent’s VaR and CVaR estimates as learning progresses on the red-pill blue-pill task for various combinations of initial VaR and CVaR guesses. We see that regardless of the initial guess, the estimates still converge. These estimates converge to the correct VaR and CVaR values, up to a constant, thereby yielding the optimal CVaR policy, as in Fig. 4a). See Appendix C for a more detailed discussion of the empirical results.

Figure: Figure 4: Rolling average-reward and reward CVaR as learning progresses when using the (risk-neutral) Differential algorithms vs. the (risk-aware) RED CVaR algorithms in the a) red-pill blue-pill, and b) inverted pendulum tasks. A solid line denotes the mean average-reward or reward CVaR, and the corresponding shaded region denotes the 95% confidence interval over 50 runs.
Refer to caption: extracted/5965996/images/results_ci.png

Figure: Figure 5: Convergence plots of the agent’s VaR and CVaR estimates as learning progresses when using the RED CVaR Q-learning algorithm on the red-pill blue-pill task with a) various combinations of initial VaR and CVaR guesses, and b) an initial guess of 0.0 for both the VaR and CVaR estimates.
Refer to caption: extracted/5965996/images/3ds.png

## 6 Discussion, limitations, and future work

In this work, we introduced reward-extended differential (or RED) reinforcement learning: a novel reinforcement learning framework that can be used to solve various subtasks simultaneously in the average-reward setting. We introduced a family of RED RL algorithms for prediction and control, and then showcased how these algorithms could be adopted to effectively and efficiently tackle the CVaR optimization problem. More specifically, we were able to use the RED RL framework to successfully learn a policy that optimized the CVaR risk measure without using an explicit bi-level optimization scheme or an augmented state-space, thereby alleviating some of the computational challenges and non-trivialities that arise when performing risk-based optimization in the episodic and discounted settings. Empirically, we showed that the RED-based CVaR algorithms fared well both in tabular and linear function approximation settings. Moreover, our experiments suggest that these algorithms are robust to the initial guesses for the subtasks and primary learning objective.

More broadly, our work has introduced a theoretically-sound framework that allows for a subtask-driven approach to reinforcement learning, where various learning problems (or subtasks) are solved simultaneously to help solve a larger, central learning problem. In this work, we showed (both theoretically and empirically) how this framework can be utilized to predict and/or optimize any arbitrary number of subtasks simultaneously in the average-reward setting. Central to this result is the novel concept of the reward-extended TD error, which is utilized in our framework to develop learning rules for the subtasks, and satisfies key theoretical properties that make it possible to solve any given subtask in a fully-online manner by minimizing the regular TD error. Moreover, we built-upon existing results from Wan et al. [] to show the almost sure convergence of tabular algorithms derived from our framework. While we have only begun to grasp the implications of our framework, we have already seen some promising indications in the CVaR case study: the ability to turn explicit bi-level optimization problems into implicit bi-level optimizations that can be solved in a fully-online manner, as well as the potential to turn certain states (that meet certain conditions) into subtasks, thereby reducing the size of the state-space.

Nonetheless, while these results are encouraging, they are subject to a number of limitations. Firstly, by nature of operating in the average-reward setting, we are subject to the somewhat-strict assumptions made about the Markov chain induced by the policy (e.g. unichain or communicating). These assumptions could restrict the applicability of our framework, as they may not always hold in practice. Similarly, our definition for a subtask requires that the associated subtask function be linear, which may also limit the applicability of our framework to simpler functions. Finally, it remains to be seen empirically how our framework performs when dealing with multiple subtasks, when taking on more complex tasks, and/or when utilizing nonlinear function approximation.

In future work, we hope to address many of these limitations, as well as explore how these promising results can be extended to other domains, beyond the risk-awareness problem. In particular, we believe that the ability to optimize various subtasks simultaneously, as well as the potential to reduce the size of the state-space, by converting certain states to subtasks (where appropriate), could help alleviate significant computational challenges in other areas moving forward.

## Acknowledgments and Disclosure of Funding

The authors would like to thank Margaret P. Chapman for insightful conversations and feedback in the early stages of this work.

## Appendix A RED RL algorithms

In this Appendix, we provide pseudocode for our RED RL algorithms. We first present tabular algorithms, whose convergence proofs are included in Appendix B, and then provide equivalent algorithms that utilize function approximation.

Figure: Algorithm 1 RED TD-Learning (Tabular)

Figure: Algorithm 2 RED Q-Learning (Tabular)

Figure: Algorithm 3 RED TD-Learning (Function Approximation)

Figure: Algorithm 4 RED Q-Learning (Function Approximation)

## Appendix B Convergence proofs

In this Appendix, we present the full convergence proofs for the tabular RED TD-learning and tabular RED Q-learning algorithms. Our general strategy is as follows: we first show that the results from Wan et al. [], which show the a.s. convergence of the value function and average-reward estimates of differential algorithms, are applicable to our algorithms. We then build upon these results to show that the subtask estimates of our algorithms converge as well.

For consistency, we adopt similar notation as Wan et al. [] for our proofs:

- •
For a given vector $x$, let $\sum x$ denote the sum of all elements in $x$, such that $\sum x\doteq\sum_{i}x(i)$.
- •
Let $\bar{r}_{*}$ denote the optimal average-reward.
- •
Let $z_{i_{*}}$ denote the corresponding optimal subtask value for subtask $z_{i}\in\mathcal{Z}$.

### B.1 Convergence proof for the tabular RED TD-learning algorithm

In this section, we present the proof for the convergence of the value function, average-reward, and subtask estimates of the RED TD-learning algorithm. Similar to what was done in Wan et al. [], we will begin by considering a general algorithm, called General RED TD. We will first define General RED TD, then show how the RED TD-learning algorithm is a special case of this algorithm. We will then provide necessary assumptions, state the convergence theorem of General RED TD, and then provide a proof for the theorem, where we show that the value function, average-reward, and subtask estimates converge, thereby showing that the RED TD-learning algorithm converges. We begin by introducing the General RED TD algorithm:

First consider an MDP $\mathcal{M}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{R},p\rangle$, a behavior policy $B$, and a target policy $\pi$. Given a state $s\in\mathcal{S}$ and discrete step $n\geq 0$, let $A_{n}(s)\sim B(\cdot\mid s)$ denote the action selected using the behavior policy, let $R_{n}(s,A_{n}(s))\in\mathcal{R}$ denote a sample of the resulting reward, and let $S^{\prime}_{n}(s,A_{n}(s))\sim p(\cdot,\cdot\mid s,a)$ denote a sample of the resulting state. Let $\{Y_{n}\}$ be a set-valued process taking values in the set of nonempty subsets of $\mathcal{S}$, such that: $Y_{n}=\{s:s$ component of the $|\mathcal{S}|$-sized table of state-value estimates, $V$, that was updated at step $n\}$. Let $\nu(n,s)\doteq\sum_{j=0}^{n}I\{s\in Y_{j}\}$, where $I$ is the indicator function, such that $\nu(n,s)$ represents the number of times $V(s)$ was updated up to step $n$.

Now, let $f$ be a valid subtask function (see Definition 4.1), such that $\tilde{R}_{n}(s,A_{n}(s))\doteq f(R_{n}(s,A_{n}(s)),Z_{1,n},Z_{2,n},\ldots,Z_{
k,n})$ for $k$ subtasks $\in\mathcal{Z}$, where $\mathcal{Z}$ is the set of subtasks, and $Z_{i,n}$ denotes the estimate of subtask $z_{i}\in\mathcal{Z}$ at step $n$. Consider an MDP with the modified reward: $\mathcal{\tilde{M}}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{\tilde{R}},p\rangle$, such that $\tilde{R}_{n}(s,A_{n}(s))\in\mathcal{\tilde{R}}$. The update rules of General RED TD for the modified MDP are as follows, for $n\geq 0$:

$$ $\displaystyle V_{n+1}(s)$ $\displaystyle\doteq V_{n}(s)+\alpha_{\nu(n,s)}\rho_{n}(s)\delta_{n}(s)I\{s\in Y _{n}\},\quad\forall s\in\mathcal{S},$ (B.1) $\displaystyle\bar{R}_{n+1}$ $\displaystyle\doteq\bar{R}_{n}+\eta_{r}\sum_{s}\alpha_{\nu(n,s)}\rho_{n}(s) \delta_{n}(s)I\{s\in Y_{n}\},$ (B.2) $\displaystyle Z_{i,n+1}$ $\displaystyle\doteq Z_{i,n}+\eta_{z_{i}}\sum_{s}\alpha_{\nu(n,s)}\rho_{n}(s) \beta_{i,n}(s)I\{s\in Y_{n}\},\quad\forall z_{i}\in\mathcal{Z},$ (B.3) $$

where,

$$ $\displaystyle\begin{split}\delta_{n}(s)&\doteq\tilde{R}_{n}(s,A_{n}(s))-\bar{R }_{n}+V_{n}(S_{n}^{\prime}(s,A_{n}(s)))-V_{n}(s)\\ &=f(R_{n}(s,A_{n}(s)),Z_{1,n},Z_{2,n},\ldots,Z_{k,n})-\bar{R}_{n}+V_{n}(S_{n}^ {\prime}(s,A_{n}(s)))-V_{n}(s),\end{split}$ (B.4) $$

and,

$$ $\displaystyle\beta_{i,n}(s)$ $\displaystyle\doteq g_{{z_{i}},n}-Z_{i,n},\quad\forall z_{i}\in\mathcal{Z}.$ (B.5) $$

Here, $\rho_{n}(s)\doteq\pi(A_{n}(s)\mid s)\,/\,B(A_{n}(s)\mid s)$ denotes the importance sampling ratio (with behavior policy $B$), $\bar{R}_{n}$ denotes the estimate of the average-reward (see Equation (2)), $\delta_{n}(s)$ denotes the TD error, $\eta_{r}$ and $\eta_{z_{i}}$ are positive scalars, $g_{{z_{i}},n}$ denotes the inverse of the TD error (i.e., Equation (B.4)) with respect to subtask estimate $Z_{i,n}$ given all other inputs when $\delta_{n}(s)=0$, and $\alpha_{\nu(n,s)}$ denotes the step size at time step $n$ for state $s$. In this case, the step size depends on the sequence $\{\alpha_{n}\}$, as well as the number of visitations to state $s$, which is denoted by $\nu(n,s)$.

We now show that the RED TD-learning algorithm is a special case of the General RED TD algorithm. Consider a sequence of experience from our MDP $\mathcal{\tilde{M}}$: $S_{t},A_{t}(S_{t}),\tilde{R}_{t+1},S_{t+1},\ldots$  . Now recall the set-valued process $\{Y_{n}\}$. If we let $n$ = time step $t$, we have:

$$ $\displaystyle Y_{t}(s)=\begin{cases}1,s=S_{t},\\ 0,\text{ otherwise,}\end{cases}$ $$

as well as $S^{\prime}_{n}(S_{t},A_{t}(S_{t}))=S_{t+1}$, $R_{n}(S_{t},A_{t})=R_{t+1}$, $\tilde{R}_{n}(S_{t},A_{t}(S_{t}))=\tilde{R}_{t+1}$.

Hence, update rules (B.1), (B.2), (B.3), (B.4), and (B.5) become:

$$ $\displaystyle V_{t+1}(S_{t})$ $\displaystyle\doteq V_{t}(S_{t})+\alpha_{\nu(t,S_{t})}\rho_{t}(S_{t})\delta_{t }\text{\ , and\ }V_{t+1}(s)\doteq V_{t}(s),\forall s\neq S_{t},$ (B.6) $\displaystyle\bar{R}_{t+1}$ $\displaystyle\doteq\bar{R}_{t}+\eta_{r}\alpha_{\nu(t,S_{t})}\rho_{t}(S_{t}) \delta_{t},$ (B.7) $\displaystyle Z_{i,t+1}$ $\displaystyle\doteq Z_{i,t}+\eta_{z_{i}}\alpha_{\nu(t,S_{t})}\rho_{t}(S_{t}) \beta_{i,t},\quad\forall z_{i}\in\mathcal{Z},$ (B.8) $\displaystyle\begin{split}\delta_{t}&\doteq\tilde{R}_{t+1}-\bar{R}_{t}+V_{t}(S _{t+1})-V_{t}(S_{t}),\\ &=f(R_{t+1},Z_{1,t},Z_{2,t},\ldots,Z_{k,t})-\bar{R}_{t}+V_{t}(S_{t+1})-V_{t}(S _{t}),\end{split}$ (B.9) $\displaystyle\beta_{i,t}$ $\displaystyle\doteq g_{{z_{i}},t}-Z_{i,t},\quad\forall z_{i}\in\mathcal{Z},$ (B.10) $$

which are RED TD-learning’s update rules with $\alpha_{\nu(t,S_{t})}$ denoting the step size at time $t$.

We now specify the assumptions on General RED TD that are needed to ensure convergence. Please refer to Wan et al. [] for an in-depth discussion on Assumptions B.1 – B.5:

###### Assumption B.1 (Unichain Assumption) .

The Markov chain induced by the target policy is unichain.

###### Assumption B.2 (Coverage Assumption) .

$B(a\mid s)>0$ if $\pi(a\mid s)>0$ for all $s\in\mathcal{S}$, $a\in\mathcal{A}$.

###### Assumption B.3 (Step Size Assumption) .

$\alpha_{n}>0$, $\sum_{n=0}^{\infty}\alpha_{n}=\infty$, $\sum_{n=0}^{\infty}\alpha_{n}^{2}<\infty$.

###### Assumption B.4 (Asynchronous Step Size Assumption 1) .

Let $[\cdot]$ denote the integer part of $(\cdot)$. For $x\in(0,1)$,

$$ $\displaystyle\sup_{i}\frac{\alpha_{[xi]}}{\alpha_{i}}<\infty$ $$

and

$$ $\displaystyle\frac{\sum_{j=0}^{[yi]}\alpha_{j}}{\sum_{j=0}^{i}\alpha_{j}}\to 1$ $$

uniformly in $y\in[x,1]$.

###### Assumption B.5 (Asynchronous step size Assumption 2) .

There exists $\Delta>0$ such that

$$ $\displaystyle\liminf_{n\to\infty}\frac{\nu(n,s)}{n+1}\geq\Delta,$ $$

a.s., for all $s\in\mathcal{S}$.

Furthermore, for all $x>0$, and

$$ $\displaystyle N(n,x)=\min\Bigg{\{}m\geq n:\sum_{i=n+1}^{m}\alpha_{i}\geq x \Bigg{\}},$ $$

the limit

$$ $\displaystyle\lim_{n\to\infty}\frac{\sum_{i=\nu(n,s)}^{\nu(N(n,x),s)}\alpha_{i }}{\sum_{i=\nu(n,s^{\prime})}^{\nu(N(n,x),s^{\prime})}\alpha_{i}}$ $$

exists a.s. for all $s,s^{\prime}$.

Assumptions B.3, B.4, and B.5, which originate from [], outline the step size requirements needed to show the convergence of stochastic approximation algorithms. Assumptions B.3 and B.4 can be satisfied with step size sequences that decrease to 0 appropriately, including $1/n$, $1/(n\log n)$, and $\log n/n$ []. Assumption B.5 first requires that the limiting ratio of visits to any given state, compared to the total number of visits to all states, is greater than or equal to some fixed positive value. The assumption then requires that the relative update frequency between any two states is finite. For instance, Assumption B.5 can be satisfied with $\alpha_{n}=1/n$ (see page 403 of [] for more information).

###### Assumption B.6 (Subtask Function Assumption) .

The subtask function, $f$, is 1) linear or piecewise linear, and 2) is invertible with respect to each input given all other inputs.

###### Assumption B.7 (Subtask Independence Assumption) .

Each subtask $z_{i}\in\mathcal{Z}$ is independent of the states and actions, and hence independent of the observed reward, $R_{n}(s,a)$, such that $\mathbb{E}[f(R_{n}(s,a),Z_{1,n},Z_{2,n},\ldots,Z_{k,n})]=f(\mathbb{E}[R_{n}(s,
a)],Z_{1,n},Z_{2,n},\ldots,Z_{k,n})$.

Assumptions B.6 and B.7 outline the subtask-related requirements. Assumption B.6 ensures that we can explicitly write out the update (B.3), and Assumption B.7 ensures that we do not break the Markov property in the process (i.e., we preserve the Markov property by ensuring that the subtasks are independent of the states and actions, and thereby also independent of the observed reward).

We next point out that it is easy to verify that under Assumption B.1, the following system of equations:

$$ $\displaystyle\begin{split}v_{\pi}(s)&=\sum_{a}\pi(a\mid s)\sum_{s^{\prime}, \tilde{r}}p(s^{\prime},\tilde{r}\mid s,a)(\tilde{r}-\bar{r}_{\pi}+v_{\pi}(s^{ \prime})),\text{ for all }s\in\mathcal{S},\\ &=\sum_{a}\pi(a\mid s)\sum_{s^{\prime},r}p(s^{\prime},r\mid s,a)(f(r,z_{1},z_{ 2},\ldots,z_{k})-\bar{r}_{\pi}+v_{\pi}(s^{\prime})),\\ \end{split}$ (B.11) $$

and,

$$ $\displaystyle\bar{r}_{\pi}-\bar{R}_{0}$ $\displaystyle=\eta_{r}\left(\sum v_{\pi}-\sum V_{0}\right),$ (B.12) $\displaystyle z_{i,\pi}-Z_{i,0}$ $\displaystyle=\eta_{i}\left(\sum v_{\pi}-\sum V_{0}\right),\text{\ for all }z_ {i}\in\mathcal{Z},$ (B.13) $$

has a unique solution of $v_{\pi}$, where $\bar{r}_{\pi}$ denotes the average-reward induced by following a given policy $\pi$, and $z_{i,\pi}$ denotes the corresponding subtask value for subtask $z_{i}\in\mathcal{Z}$. Denote this unique solution of $v_{\pi}$ as $v_{\infty}$.

We are now ready to state the convergence theorem:

###### Theorem B.1.1 (Convergence of General RED TD) .

If Assumptions B.1 – B.7 hold, then General RED TD (Equations (B.1) – (B.5)) converges a.s., $\bar{R}_{n}$ to $\bar{r}_{\pi}$, $Z_{i,n}$ to $z_{i,\pi}\;\forall z_{i}\in\mathcal{Z}$, and $V_{n}$ to $v_{\infty}$.

We prove this theorem in the following section. To do so, we first show that General RED TD is of the same form as General Differential TD from Wan et al. [], which consequently allows us to apply their convergence results for the value function and average-reward estimates of General Differential TD to General RED TD. We then build upon these results, using similar techniques as Wan et al. [], to show that the subtask estimates converge as well.

###### Assumption B.1 (Unichain Assumption) .

###### Assumption B.2 (Coverage Assumption) .

###### Assumption B.3 (Step Size Assumption) .

###### Assumption B.4 (Asynchronous Step Size Assumption 1) .

###### Assumption B.5 (Asynchronous step size Assumption 2) .

###### Assumption B.6 (Subtask Function Assumption) .

###### Assumption B.7 (Subtask Independence Assumption) .

###### Theorem B.1.1 (Convergence of General RED TD) .

#### B.1.1 Proof of Theorem B.1.1

Convergence of the average-reward and state-value function estimates:

Consider the increment to $\bar{R}_{n}$ at each step. We can see from Equation (B.2) that the increment is $\eta_{r}$ times the increment to $V_{n}$. As such, as was done in Wan et al. [], we can write the cumulative increment as follows:

$$ $\displaystyle\bar{R}_{n}-\bar{R}_{0}$ $\displaystyle=\eta_{r}\sum_{j=0}^{n-1}\sum_{s}\alpha_{\nu(j,s)}\rho_{j}(s) \delta_{j}(s)I\{s\in Y_{j}\}$ $\displaystyle=\eta_{r}\left(\sum V_{n}-\sum V_{0}\right)$ $\displaystyle\implies\bar{R}_{n}$ $\displaystyle=\eta_{r}\sum V_{n}-\eta_{r}\sum V_{0}+\bar{R}_{0}=\eta_{r}\sum V _{n}-c,$ (B.14) $\displaystyle\text{ where }c$ $\displaystyle\doteq\eta_{r}\sum V_{0}-\bar{R}_{0}.$ (B.15) $$

We can then substitute $\bar{R}_{n}$ in (B.1) with (B.14) $\forall s\in\mathcal{S}$, which yields:

$$ $\displaystyle\begin{split}&V_{n+1}(s)=V_{n}(s)+\ldots\,\\ &\quad\alpha_{\nu(n,s)}\rho_{n}(s)\left(\tilde{R}_{n}(s,A_{n}(s))+V_{n}(S_{n}^ {\prime}(s,A_{n}(s)))-V_{n}(s)-\eta\sum V_{n}+c\right)I\{s\in Y_{n}\}\\ \\ &V_{n+1}(s)=V_{n}(s)+\ldots\,\\ &\quad\alpha_{\nu(n,s)}\rho_{n}(s)\left(\hat{R}_{n}(s,A_{n}(s))+V_{n}(S_{n}^{ \prime}(s,A_{n}(s)))-V_{n}(s)-\eta\sum V_{n}\right)I\{s\in Y_{n}\},\end{split}$ $$

where $\hat{R}_{n}(s,A_{n}(s))\doteq\tilde{R}_{n}(s,A_{n}(s))+c=f(R_{n}(s,A_{n}(s)),Z
_{1,n},Z_{2,n},\ldots,Z_{k,n})+c$.

Equation (B.1.1) is now in the same form as Equation (B.37) (i.e., General Differential TD) from Wan et al. [], who showed that the equation converges a.s. $V_{n}$ to $v_{\infty}$ as $n\to\infty$. Moreover, from this result, Wan et al. [] showed that $\bar{R}_{n}$ converges a.s. to $\bar{r}_{\pi}$ as $n\to\infty$. Given that General RED TD adheres to all the assumptions listed for General Differential TD in Wan et al. [], these convergence results apply to General RED TD.

Convergence of the subtask estimates:

Consider the increment to $Z_{i,n}$ (for an arbitrary subtask $z_{i}\in\mathcal{Z}$) at each step. Given Assumptions B.6 and B.7 (and subsequently Corollary 4.1), we can write the increment in Equation (B.3) as some constant, subtask-specific fraction of the increment to $V_{n}$. Consequently, we can write the cumulative increment as follows:

$$ $\displaystyle Z_{i,n}-Z_{i,0}$ $\displaystyle=\eta_{z_{i}}\sum_{j=0}^{n-1}\sum_{s}\alpha_{\nu(j,s)}\rho_{j}(s) \beta_{i,j}(s)I\{s\in Y_{j}\}$ $\displaystyle=\eta_{z_{i}}\sum_{j=0}^{n-1}\sum_{s}\alpha_{\nu(j,s)}\rho_{j}(s) b_{i}\delta_{j}(s)I\{s\in Y_{j}\}$ $\displaystyle=\eta_{i}\left(\sum V_{n}-\sum V_{0}\right)$ $\displaystyle\implies Z_{i,n}$ $\displaystyle=\eta_{i}\sum V_{n}-\eta_{i}\sum V_{0}+Z_{i,0}=\eta_{i}\sum V_{n} -c,$ (B.17) $$

where,

$$ $\displaystyle c$ $\displaystyle\doteq\eta_{i}\sum V_{0}-Z_{i,0},\text{ and}$ (B.18) $\displaystyle\eta_{i}$ $\displaystyle\doteq\eta_{z_{i}}b_{i}.$ (B.19) $$

Now, let $f(Z_{i,n})$ be shorthand for the subtask function (i.e., $\tilde{R}_{n}(s,A_{n}(s))$). We can substitute $Z_{i,n}$ in (B.1) with (B.17) $\forall s\in\mathcal{S}$ as follows:

$$ $\displaystyle\begin{split}&V_{n+1}(s)=V_{n}(s)+\,\ldots\\ &\quad\alpha_{\nu(n,s)}\rho_{n}(s)\left(\tilde{R}_{n}(s,A_{n}(s))-\bar{R}+V_{n }(S_{n}^{\prime}(s,A_{n}(s)))-V_{n}(s)\right)I\{s\in Y_{n}\}\\ \\ \implies&V_{n+1}(s)=V_{n}(s)+\,\ldots\\ &\quad\alpha_{\nu(n,s)}\rho_{n}(s)\left(f(Z_{i,n})-\bar{R}+V_{n}(S_{n}^{\prime }(s,A_{n}(s)))-V_{n}(s)\right)I\{s\in Y_{n}\}\\ \\ \implies&V_{n+1}(s)=V_{n}(s)+\,\ldots\\ &\quad\alpha_{\nu(n,s)}\rho_{n}(s)\left(f(\underbrace{\eta_{i}\sum V_{n}}_{ \hat{Z}_{i,n}}-c)-\bar{R}+V_{n}(S_{n}^{\prime}(s,A_{n}(s)))-V_{n}(s)\right)I\{ s\in Y_{n}\}\\ \\ \implies&V_{n+1}(s)=V_{n}(s)+\,\ldots\\ &\quad\alpha_{\nu(n,s)}\rho_{n}(s)\left(\hat{f}(\hat{Z}_{i,n})-\bar{R}+V_{n}(S _{n}^{\prime}(s,A_{n}(s)))-V_{n}(s)\right)I\{s\in Y_{n}\}\\ \\ \implies&V_{n+1}(s)=V_{n}(s)+\,\ldots\\ &\quad\alpha_{\nu(n,s)}\rho_{n}(s)\left(\hat{R}_{n}-\bar{R}+V_{n}(S_{n}^{ \prime}(s,A_{n}(s)))-V_{n}(s)\right)I\{s\in Y_{n}\},\end{split}$ $$

where, $\hat{R}_{n}\doteq\hat{f}(\hat{Z}_{i,n})=f(Z_{i,n}+c)=h(\tilde{R}_{n})$. Here, $h(\tilde{R}_{n})$ corresponds to the change in $\tilde{R}_{n}$ due to shifting subtask $Z_{i,n}$ by $c$. Denote the inverse of $h(\tilde{R}_{n})$ (which exists given Assumption B.6) as $h^{-1}$.

Now consider an MDP, $\hat{\mathcal{M}}$, which has rewards, $\mathcal{\hat{R}}$, corresponding to rewards modified by $h$ from the MDP $\mathcal{\tilde{M}}$, has the same state and action spaces as $\mathcal{\tilde{M}}$, and has the transition probabilities defined as:

$$ $\displaystyle\hat{p}(s^{\prime},h(\hat{r})\mid s,a)\doteq p(s^{\prime},\tilde{ r}\mid s,a),$ (B.21) $$

such that $\hat{\mathcal{M}}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{\hat{R}},\hat{p}\rangle$. It is easy to check that the unichain assumption holds for the transformed MDP $\hat{\mathcal{M}}$. As such, and given Assumptions B.6 and B.7, the average-reward induced by following policy $\pi$ for the MDP $\hat{\mathcal{M}}$, $\hat{\bar{r}}_{\pi}$, can be written as follows:

$$ $\displaystyle\hat{\bar{r}}_{\pi}=h(\bar{r}_{\pi}).$ (B.22) $$

Now, because

$$ $\displaystyle v_{\infty}(s)$ $\displaystyle=\sum_{a}\pi(a\mid s)\sum_{s^{\prime},\tilde{r}}p(s^{\prime}, \tilde{r}\mid s,a)(\tilde{r}+v_{\infty}(s^{\prime})-\bar{r}_{\pi})\quad\text{( from \eqref{td_system_of_eqns})}$ $\displaystyle=\sum_{a}\pi(a\mid s)\sum_{s^{\prime},\tilde{r}}p(s^{\prime}, \tilde{r}\mid s,a)(\tilde{r}+v_{\infty}(s^{\prime})-h^{-1}(\hat{\bar{r}}_{\pi} ))\quad\text{(from \eqref{td_z_star_modified_vs_z_star})}$ $\displaystyle=\sum_{a}\pi(a\mid s)\sum_{s^{\prime},\tilde{r}}p(s^{\prime}, \tilde{r}\mid s,a)(h(\tilde{r})+v_{\infty}(s^{\prime})-\hat{\bar{r}}_{\pi}) \quad\text{(by properties of $h$)}$ $\displaystyle=\sum_{a}\pi(a\mid s)\sum_{s^{\prime},\tilde{r}}\hat{p}(s^{\prime },\tilde{r}\mid s,a)(\tilde{r}+v_{\infty}(s^{\prime})-\hat{\bar{r}}_{\pi}) \quad\text{(from \eqref{td_z_probs_modified_by_h})},$ $$

we can see that $v_{\infty}$ is a solution of not just the state-value Bellman equation for the MDP $\mathcal{\tilde{M}}$, but also the state-value Bellman equation for the transformed MDP $\hat{\mathcal{M}}$.

Next, we can write the subtask value induced by following policy $\pi$ for the MDP $\hat{\mathcal{M}}$, $\hat{z_{i}}_{,\pi}$, as follows:

$$ $\displaystyle\hat{z_{i}}_{,\pi}=z_{i,\pi}+c.$ (B.23) $$

We can then combine Equations (B.13), (B.18), and (B.23), which yields:

$$ $\displaystyle\hat{z_{i}}_{,\pi}=\eta_{i}\sum v_{\infty}.$ (B.24) $$

Next, we can combine Equation (B.17) with the result from Wan et al. [] which shows that $V_{n}\to v_{\infty}$, which yields:

$$ $\displaystyle Z_{i,n}\to\eta_{i}\sum v_{\infty}-c.$ (B.25) $$

Moreover, because $\hat{z_{i}}_{,\pi}=\eta_{i}\sum v_{\infty}$ (Equation (B.24)), we have:

$$ $\displaystyle Z_{i,n}\to\hat{z_{i}}_{,\pi}-c.$ (B.26) $$

Finally, because $\hat{z_{i}}_{,\pi}=z_{i,\pi}+c$ (Equation (B.23)), we have:

$$ $\displaystyle Z_{i,n}\to z_{i,\pi}\text{\ \ a.s. as \ \ }n\to\infty.$ (B.27) $$

This completes the proof of Theorem B.1.1.

### B.2 Convergence proof for the tabular RED Q-learning algorithm

In this section, we present the proof for the convergence of the value function, average-reward, and subtask estimates of the RED Q-learning algorithm. Similar to what was done in Wan et al. [], we will begin by considering a general algorithm, called General RED Q. We will first define General RED Q, then show how the RED Q-learning algorithm is a special case of this algorithm. We will then provide necessary assumptions, state the convergence theorem of General RED Q, and then provide a proof for the theorem, where we show that the value function, average-reward, and subtask estimates converge, thereby showing that the RED Q-learning algorithm converges. We begin by introducing the General RED Q algorithm:

First consider an MDP $\mathcal{M}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{R},p\rangle$. Given a state $s\in\mathcal{S}$, action $a\in\mathcal{A}$, and discrete step $n\geq 0$, let $R_{n}(s,a)\in\mathcal{R}$ denote a sample of the resulting reward, and let $S^{\prime}_{n}(s,a)\sim p(\cdot,\cdot\mid s,a)$ denote a sample of the resulting state. Let $\{Y_{n}\}$ be a set-valued process taking values in the set of nonempty subsets of $\mathcal{S}\times\mathcal{A}$, such that: $Y_{n}=\{(s,a):(s,a)$ component of the $|\mathcal{S}\times\mathcal{A}|$-sized table of state-action value estimates, $Q$, that was updated at step $n\}$. Let $\nu(n,s,a)\doteq\sum_{j=0}^{n}I\{(s,a)\in Y_{j}\}$, where $I$ is the indicator function, such that $\nu(n,s,a)$ represents the number of times the $(s,a)$ component of $Q$ was updated up to step $n$.

Now, let $f$ be a valid subtask function (see Definition 4.1), such that $\tilde{R}_{n}(s,a)\doteq f(R_{n}(s,a),Z_{1,n},Z_{2,n},\ldots,Z_{n,k})$ for $k$ subtasks $\in\mathcal{Z}$, where $\mathcal{Z}$ is the set of subtasks, and $Z_{i,n}$ denotes the estimate of subtask $z_{i}\in\mathcal{Z}$ at step $n$. Consider an MDP with the modified reward: $\mathcal{\tilde{M}}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{\tilde{R}},p\rangle$, such that $\tilde{R}_{n}(s,a)\in\mathcal{\tilde{R}}$. The update rules of General RED Q for the modified MDP are as follows:

$$ $\displaystyle Q_{n+1}(s,a)$ $\displaystyle\doteq Q_{n}(s,a)+\alpha_{\nu(n,s,a)}\delta_{n}(s,a)I\{(s,a)\in Y _{n}\},\quad\forall s\in\mathcal{S},a\in\mathcal{A},$ (B.28) $\displaystyle\bar{R}_{n+1}$ $\displaystyle\doteq\bar{R}_{n}+\eta_{r}\sum_{s,a}\alpha_{\nu(n,s,a)}\delta_{n} (s,a)I\{(s,a)\in Y_{n}\},$ (B.29) $\displaystyle Z_{i,n+1}$ $\displaystyle\doteq Z_{i,n}+\eta_{z_{i}}\sum_{s,a}\alpha_{\nu(n,s,a)}\beta_{i, n}(s,a)I\{(s,a)\in Y_{n}\},\quad\forall z_{i}\in\mathcal{Z}$ (B.30) $$

where,

$$ $\displaystyle\begin{split}\delta_{n}(s,a)&\doteq\tilde{R}_{n}(s,a)-\bar{R}_{n} +\max_{a^{\prime}}Q_{n}(S_{n}^{\prime}(s,a),a^{\prime})-Q_{n}(s,a)\\ &=f(R_{n}(s,a),Z_{1,n},Z_{2,n},\ldots,Z_{k,n})-\bar{R}_{n}+\max_{a^{\prime}}Q_ {n}(S_{n}^{\prime}(s,a),a^{\prime})-Q_{n}(s,a),\end{split}$ (B.31) $$

and,

$$ $\displaystyle\beta_{i,n}(s,a)$ $\displaystyle\doteq g_{{z_{i}},n}-Z_{i,n},\quad\forall z_{i}\in\mathcal{Z}.$ (B.32) $$

Here, $\bar{R}_{n}$ denotes the estimate of the average-reward (see Equation
(2)), $\delta_{n}(s,a)$ denotes the TD error, $\eta_{r}$ and $\eta_{z_{i}}$ are positive scalars, $g_{{z_{i}},n}$ denotes the inverse of the TD error (i.e., Equation (B.31)) with respect to subtask estimate $Z_{i,n}$ given all other inputs when $\delta_{n}(s,a)=0$, and $\alpha_{\nu(n,s,a)}$ denotes the step size at time step $n$ for state-action pair $(s,a)$. In this case, the step size depends on the sequence $\{\alpha_{n}\}$, as well as the number of visitations to the state-action pair $(s,a)$, which is denoted by $\nu(n,s,a)$.

We now show that the RED Q-learning algorithm is a special case of the General RED Q algorithm. Consider a sequence of experience from our MDP $\mathcal{\tilde{M}}$: $S_{t},A_{t},\tilde{R}_{t+1},S_{t+1},\ldots$  . Now recall the set-valued process $\{Y_{n}\}$. If we let $n$ = time step $t$, we have:

$$ $\displaystyle Y_{t}(s,a)=\begin{cases}1,s=S_{t}\text{ and }a=A_{t},\\ 0,\text{ otherwise,}\end{cases}$ $$

as well as $S^{\prime}_{n}(S_{t},A_{t})=S_{t+1}$, $R_{n}(S_{t},A_{t})=R_{t+1}$, and $\tilde{R}_{n}(S_{t},A_{t})=\tilde{R}_{t+1}$.

Hence, update rules (B.28), (B.29), (B.30), (B.31), and (B.32) become:

$$ $\displaystyle Q_{t+1}(S_{t},A_{t})$ $\displaystyle\doteq Q_{t}(S_{t},A_{t})+\alpha_{\nu(t,S_{t},A_{t})}\delta_{t} \text{, and\ }Q_{t+1}(s,a)\doteq Q_{t}(s,a),\forall s\neq S_{t},a\neq A_{t},$ (B.33) $\displaystyle\bar{R}_{t+1}$ $\displaystyle\doteq\bar{R}_{t}+\eta_{r}\alpha_{\nu(t,S_{t},A_{t})}\delta_{t},$ (B.34) $\displaystyle Z_{i,t+1}$ $\displaystyle\doteq Z_{i,t}+\eta_{z_{i}}\alpha_{\nu(t,S_{t},A_{t})}\beta_{i,t} ,\quad\forall z_{i}\in\mathcal{Z},$ (B.35) $\displaystyle\begin{split}\delta_{t}&\doteq\tilde{R}_{t+1}-\bar{R}_{t}+\max_{a ^{\prime}}Q_{t}(S_{t+1},a^{\prime})-Q_{t}(S_{t},A_{t}),\\ &=f(R_{t+1},Z_{1,t},Z_{2,t},\ldots,Z_{k,t})-\bar{R}_{t}+\max_{a^{\prime}}Q_{t} (S_{t+1},a^{\prime})-Q_{t}(S_{t},A_{t}),\end{split}$ (B.36) $\displaystyle\beta_{i,t}$ $\displaystyle\doteq g_{{z_{i}},t}-Z_{i,t},\quad\forall z_{i}\in\mathcal{Z},$ (B.37) $$

which are RED Q-learning’s update rules with $\alpha_{\nu(t,S_{t},A_{t})}$ denoting the step size at time $t$.

We now specify the assumptions on General RED Q that are needed to ensure convergence. Please refer to Wan et al. [] for an in-depth discussion on these assumptions:

###### Assumption B.8 (Communicating Assumption) .

The MDP has a single communicating class. That is, each state in the MDP is accessible from every other state under some deterministic stationary policy.

###### Assumption B.9 (Action-Value Function Uniqueness) .

There exists a unique solution of $q$ only up to a constant in the Bellman equation (5).

###### Assumption B.10 (Asynchronous Step Size Assumption 3) .

There exists $\Delta>0$ such that

$$ $\displaystyle\liminf_{n\to\infty}\frac{\nu(n,s,a)}{n+1}\geq\Delta,$ $$

a.s., for all $s\in\mathcal{S},a\in\mathcal{A}$.

Furthermore, for all $x>0$, and

$$ $\displaystyle N(n,x)=\min\Bigg{\{}m>n:\sum_{i=n+1}^{m}\alpha_{i}\geq x\Bigg{\}},$ $$

the limit

$$ $\displaystyle\lim_{n\to\infty}\frac{\sum_{i=\nu(n,s,a)}^{\nu(N(n,x),s,a)} \alpha_{i}}{\sum_{i=\nu(n,s^{\prime},a^{\prime})}^{\nu(N(n,x),s^{\prime},a^{ \prime})}\alpha_{i}}$ $$

exists a.s. for all $s,s^{\prime},a,a^{\prime}$.

We next point out that it is easy to verify that under Assumption B.8, the following system of equations:

$$ $\displaystyle\begin{split}q_{\pi}(s,a)&=\sum_{s^{\prime},\tilde{r}}p(s^{\prime },\tilde{r}\mid s,a)(\tilde{r}-\bar{r}_{\pi}+\max_{a^{\prime}}q_{\pi}(s,a)), \quad\forall s\in\mathcal{S},a\in\mathcal{A},\\ &=\sum_{s^{\prime},r}p(s^{\prime},r\mid s,a)(f(r,z_{1},z_{2},\ldots,z_{k})- \bar{r}_{\pi}+\max_{a^{\prime}}q_{\pi}(s,a)),\\ \end{split}$ (B.38) $$

and,

$$ $\displaystyle\bar{r}_{*}-\bar{R}_{0}$ $\displaystyle=\eta_{r}\left(\sum q_{\pi}-\sum Q_{0}\right),$ (B.39) $\displaystyle z_{i_{*}}-Z_{i,0}$ $\displaystyle=\eta_{i}\left(\sum q_{\pi}-\sum Q_{0}\right),\quad\forall z_{i} \in\mathcal{Z},$ (B.40) $$

has a unique solution for $q_{\pi}$, where $\bar{r}_{*}$ denotes the optimal average-reward, and $z_{i_{*}}$ denotes the corresponding optimal subtask value for subtask $z_{i}\in\mathcal{Z}$. Denote this unique solution for $q_{\pi}$ as $q_{*}$.

We are now ready to state the convergence theorem:

###### Theorem B.2.1 (Convergence of General RED Q) .

If Assumptions B.3, B.4, B.6, B.7, B.8, B.9, and B.10 hold, then the General RED Q algorithm (Equations B.28–B.32) converges a.s. $\bar{R}_{n}$ to $\bar{r}_{*}$, $Z_{i,n}$ to $z_{i_{*}}\;\forall z_{i}\in\mathcal{Z}$, $Q_{n}$ to $q_{*}$, $\bar{r}_{\pi_{t}}$ to $\bar{r}_{*}$, and $z_{i,\pi_{t}}$ to $z_{i_{*}}\;\forall z_{i}\in\mathcal{Z}$, where $\pi_{t}$ is any greedy policy with respect to $Q_{t}$, and $z_{i,\pi_{t}}$ denotes the subtask value induced by following policy $\pi_{t}$.

We prove this theorem in the following section. To do so, we first show that General RED Q is of the same form as General Differential Q from Wan et al. [], which consequently allows us to apply their convergence results for the value function and average-reward estimates of General Differential Q to General RED Q. We then build upon these results, using similar techniques as Wan et al. [], to show that the subtask estimates converge as well.

###### Assumption B.8 (Communicating Assumption) .

###### Assumption B.9 (Action-Value Function Uniqueness) .

###### Assumption B.10 (Asynchronous Step Size Assumption 3) .

###### Theorem B.2.1 (Convergence of General RED Q) .

#### B.2.1 Proof of Theorem B.2.1

Convergence of the average-reward and state-action value function estimates:

Consider the increment to $\bar{R}_{n}$ at each step. We can see from Equation (B.29) that the increment is $\eta_{r}$ times the increment to $Q_{n}$. As such, as was done in Wan et al. [], we can write the cumulative increment as follows:

$$ $\displaystyle\bar{R}_{n}-\bar{R}_{0}$ $\displaystyle=\eta_{r}\sum_{j=0}^{n-1}\sum_{s,a}\alpha_{\nu(j,s,a)}\delta_{j}( s,a)I\{(s,a)\in Y_{j}\}$ $\displaystyle=\eta_{r}\left(\sum Q_{n}-\sum Q_{0}\right)$ $\displaystyle\implies\bar{R}_{n}$ $\displaystyle=\eta_{r}\sum Q_{n}-\eta_{r}\sum Q_{0}+\bar{R}_{0}=\eta_{r}\sum Q _{n}-c,$ (B.41) $\displaystyle\text{ where }c$ $\displaystyle\doteq\eta_{r}\sum Q_{0}-\bar{R}_{0}.$ (B.42) $$

We can then substitute $\bar{R}_{n}$ in (B.28) with (B.41) $\forall s\in\mathcal{S},a\in\mathcal{A}$, which yields:

$$ $\displaystyle\begin{split}&Q_{n+1}(s,a)=Q_{n}(s,a)+\,\ldots\\ &\quad\alpha_{\nu(n,s,a)}\left(\tilde{R}_{n}(s,a)+\max_{a^{\prime}}Q_{n}(S_{n} ^{\prime}(s,a),a^{\prime})-Q_{n}(s,a)-\eta_{r}\sum Q_{n}+c\right)I\{(s,a)\in Y _{n}\}\\ \\ &Q_{n+1}(s,a)=Q_{n}(s,a)+\,\ldots\\ &\quad\alpha_{\nu(n,s,a)}\left(\hat{R}_{n}(s,a)+\max_{a^{\prime}}Q_{n}(S^{ \prime}_{n}(s,a),a^{\prime})-Q_{n}(s,a)-\eta_{r}\sum Q_{n}\right)I\{(s,a)\in Y _{n}\},\end{split}$ $$

where, $\hat{R}_{n}(s,a)\doteq\tilde{R}_{n}(s,a)+c=f(R_{n}(s,a),Z_{1,n},Z_{2,n},\ldots
,Z_{k,n})+c$.

Equation (B.2.1) is now in the same form as Equation (B.14) (i.e., General Differential Q) from Wan et al. [], who showed that the equation converges a.s. $Q_{n}$ to $q_{*}$ as $n\to\infty$. Moreover, from this result, Wan et al. [] showed that $\bar{R}_{n}$ converges a.s. to $\bar{r}_{*}$ as $n\to\infty$, and that $\bar{r}_{\pi_{t}}$ converges a.s. to $\bar{r}_{*}$, where $\pi_{t}$ is a greedy policy with respect to $Q_{t}$. Given that General RED Q adheres to all the assumptions listed for General Differential Q in Wan et al. [], these convergence results apply to General RED Q.

Convergence of the subtask estimates:

Consider the increment to $Z_{i,n}$ (for an arbitrary subtask $z_{i}\in\mathcal{Z}$) at each step. Given Assumptions B.6 and B.7 (and subsequently Corollary 4.1), we can write the increment in Equation (B.30) as some constant, subtask-specific fraction of the increment to $Q_{n}$. Consequently, we can write the cumulative increment as follows:

$$ $\displaystyle Z_{i,n}-Z_{i,0}$ $\displaystyle=\eta_{z_{i}}\sum_{j=0}^{n-1}\sum_{s,a}\alpha_{\nu(j,s,a)}\beta_{ i,j}(s,a)I\{(s,a)\in Y_{j}\}$ $\displaystyle=\eta_{z_{i}}\sum_{j=0}^{n-1}\sum_{s,a}\alpha_{\nu(j,s,a)}b_{i} \delta_{j}(s,a)I\{(s,a)\in Y_{j}\}$ $\displaystyle=\eta_{i}\left(\sum Q_{n}-\sum Q_{0}\right)$ $\displaystyle\implies Z_{i,n}$ $\displaystyle=\eta_{i}\sum Q_{n}-\eta_{i}\sum Q_{0}+Z_{i,0}=\eta_{i}\sum Q_{n} -c,$ (B.44) $$

where,

$$ $\displaystyle c$ $\displaystyle\doteq\eta_{i}\sum Q_{0}-Z_{i,0},\text{ and}$ (B.45) $\displaystyle\eta_{i}$ $\displaystyle\doteq\eta_{z_{i}}b_{i}.$ (B.46) $$

Now, let $f(Z_{i,n})$ be shorthand for the subtask function (i.e., $\tilde{R}_{n}(s,a)$). We can substitute $Z_{i,n}$ in (B.28) with (B.44) $\forall s\in\mathcal{S},a\in\mathcal{A}$ as follows:

$$ $\displaystyle\begin{split}&Q_{n+1}(s,a)=Q_{n}(s,a)+\,\ldots\\ &\quad\alpha_{\nu(n,s,a)}\left(\tilde{R}_{n}(s,a)-\bar{R}+\max_{a^{\prime}}Q_{ n}(S_{n}^{\prime}(s,a),a^{\prime})-Q_{n}(s,a)\right)I\{(s,a)\in Y_{n}\}\\ \\ \implies&Q_{n+1}(s,a)=Q_{n}(s,a)+\,\ldots\\ &\quad\alpha_{\nu(n,s,a)}\left(f(Z_{i,n})-\bar{R}+\max_{a^{\prime}}Q_{n}(S_{n} ^{\prime}(s,a),a^{\prime})-Q_{n}(s,a)\right)I\{(s,a)\in Y_{n}\}\\ \\ \implies&Q_{n+1}(s,a)=Q_{n}(s,a)+\,\ldots\\ &\quad\alpha_{\nu(n,s,a)}\left(f(\underbrace{\eta_{i}\sum Q_{n}}_{\hat{Z}_{i,n }}-c)-\bar{R}+\max_{a^{\prime}}Q_{n}(S_{n}^{\prime}(s,a),a^{\prime})-Q_{n}(s,a )\right)I\{(s,a)\in Y_{n}\}\\ \\ \implies&Q_{n+1}(s,a)=Q_{n}(s,a)+\,\ldots\\ &\quad\alpha_{\nu(n,s,a)}\left(\hat{f}(\hat{Z}_{i,n})-\bar{R}+\max_{a^{\prime} }Q_{n}(S_{n}^{\prime}(s,a),a^{\prime})-Q_{n}(s,a)\right)I\{(s,a)\in Y_{n}\}\\ \\ \end{split}$ $$

$$ $\displaystyle\begin{split}\implies&Q_{n+1}(s,a)=Q_{n}(s,a)+\,\ldots\\ &\quad\alpha_{\nu(n,s,a)}\left(\hat{R}_{n}-\bar{R}+\max_{a^{\prime}}Q_{n}(S^{ \prime}_{n}(s,a),a^{\prime})-Q_{n}(s,a)\right)I\{(s,a)\in Y_{n}\},\end{split}$ $$

where, $\hat{R}_{n}\doteq\hat{f}(\hat{Z}_{i,n})=f(Z_{i,n}+c)=h(\tilde{R}_{n})$. Here, $h(\tilde{R}_{n})$ corresponds to the change in $\tilde{R}_{n}$ due to shifting subtask $Z_{i,n}$ by $c$. Denote the inverse of $h(\tilde{R}_{n})$ (which exists given Assumption B.6) as $h^{-1}$.

Now consider an MDP, $\hat{\mathcal{M}}$, which has rewards, $\mathcal{\hat{R}}$, corresponding to rewards modified by $h$ from the MDP $\mathcal{\tilde{M}}$, has the same state and action spaces as $\mathcal{\tilde{M}}$, and has the transition probabilities defined as:

$$ $\displaystyle\hat{p}\left(s^{\prime},h(\tilde{r})\mid s,a\right)\doteq p(s^{ \prime},\tilde{r}\mid s,a),$ (B.48) $$

such that $\hat{\mathcal{M}}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{\hat{R}},\hat{p}\rangle$. It is easy to check that the communicating assumption holds for the transformed MDP $\hat{\mathcal{M}}$. As such, and given Assumptions B.6 and B.7, the optimal average-reward for the MDP $\hat{\mathcal{M}}$, $\hat{\bar{r}}_{*}$, can be written as follows:

$$ $\displaystyle\hat{\bar{r}}_{*}=h(\bar{r}_{*}).$ (B.49) $$

Now, because

$$ $\displaystyle q_{*}(s,a)$ $\displaystyle=\sum_{s^{\prime},\tilde{r}}p(s^{\prime},\tilde{r}\mid s,a)( \tilde{r}+\max_{a^{\prime}}q_{*}(s^{\prime},a^{\prime})-\bar{r}_{*})\quad\text {(from \eqref{q_system_of_eqns})}$ $\displaystyle=\sum_{s^{\prime},\tilde{r}}p(s^{\prime},\tilde{r}\mid s,a)( \tilde{r}+\max_{a^{\prime}}q_{*}(s^{\prime},a^{\prime})-h^{-1}(\hat{\bar{r}}_{ *}))\quad\text{(from \eqref{q_z_star_modified_vs_z_star})}$ $\displaystyle=\sum_{s^{\prime},\tilde{r}}p(s^{\prime},\tilde{r}\mid s,a)(h( \tilde{r})+\max_{a^{\prime}}q_{*}(s^{\prime},a^{\prime})-\hat{\bar{r}}_{*}) \quad\text{(by properties of $h$)}$ $\displaystyle=\sum_{s^{\prime},\tilde{r}}\hat{p}(s^{\prime},\tilde{r}\mid s,a) (\tilde{r}+\max_{a^{\prime}}q_{*}(s^{\prime},a^{\prime})-\hat{\bar{r}}_{*}) \quad\text{(from \eqref{q_z_probs_modified_by_h})},$ $$

we can see that $q_{*}$ is a solution of not just the state-action value Bellman equation for the MDP $\mathcal{\tilde{M}}$, but also the state-action value Bellman equation for the transformed MDP $\hat{\mathcal{M}}$.

Next, we can write the optimal subtask value for the MDP $\hat{\mathcal{M}}$, $\hat{z}_{i_{*}}$, as follows:

$$ $\displaystyle\hat{z}_{i_{*}}=z_{i_{*}}+c.$ (B.50) $$

We can then combine Equations (B.40), (B.45), and (B.50), which yields:

$$ $\displaystyle\hat{z}_{i_{*}}=\eta_{i}\sum q_{*}.$ (B.51) $$

Next, we can combine Equation (B.44) with the result from Wan et al. [] which shows that $Q_{n}\to q_{*}$, which yields:

$$ $\displaystyle Z_{i,n}\to\eta_{i}\sum q_{*}-c.$ (B.52) $$

Moreover, because $\eta_{i}\sum q_{*}=\hat{z}_{i_{*}}$ (Equation (B.51)), we have:

$$ $\displaystyle Z_{i,n}\to\hat{z}_{i_{*}}-c.$ (B.53) $$

Finally, because $\hat{z}_{i_{*}}=z_{i_{*}}+c$ (Equation (B.50)), we have:

$$ $\displaystyle Z_{i,n}\to z_{i_{*}}\text{\ \ a.s. as \ \ }n\to\infty.$ (B.54) $$

We conclude by considering $z_{i,\pi_{t}}\;\forall z_{i}\in\mathcal{Z}$, where $\pi_{t}$ is a greedy policy with respect to $Q_{t}$. Given Definition 4.1, and that $\bar{r}_{\pi_{t}}\to\bar{r}_{*}$ a.s., it directly follows that $z_{i,\pi_{t}}\to z_{i_{*}}\;\forall z_{i}\in\mathcal{Z}$ a.s.

This completes the proof of Theorem  B.2.1.

## Appendix C Numerical experiments

This Appendix contains details regarding the numerical experiments performed as part of this work. We discuss the experiments performed in the red-pill blue-pill environment (see Appendix D for more details on the red-pill blue-pill environment), as well as the experiments performed in the inverted pendulum environment. The aim of the experiments was to contrast and compare the RED RL algorithms with the Differential learning algorithms from Wan et al. [] in the context of CVaR optimization. In particular, we aimed to show how the RED RL algorithms could be utilized to optimize for CVaR (without the use of an augmented state-space or an explicit bi-level optimization scheme), and contrast the results to those of the Differential learning algorithms, which served as a sort of ‘baseline’ to illustrate how our risk-aware approach contrasts a risk-neutral approach. We begin by first describing how we leveraged the RED RL framework for CVaR optimization.

### C.1 Leveraging the RED RL framework for CVaR optimization

As mentioned in Section 4.1, our goal is to learn a policy that induces a stationary reward distribution with an optimal reward CVaR (instead of the regular average-reward). Here, the reward CVaR, which can be interpreted as an expectation, is our primary control objective (i.e., the $\bar{r}_{\pi}$ that we want to optimize), and the value-at-risk, VaR ($b$ in Equation (10)), is our subtask. For convenience, Equation (10) is displayed below as Equation (C.1) in this Appendix:

$$ $\displaystyle\text{CVaR}_{\tau}(R)$ $\displaystyle=\max_{b\in\mathbb{R}}\mathbb{E}[b-\frac{1}{\tau}(b-R)^{+}]$ (C.1a) $\displaystyle=\mathbb{E}[\text{VaR}_{\tau}(R)-\frac{1}{\tau}(\text{VaR}_{\tau} (R)-R)^{+}],$ (C.1b) $$

where the CVaR parameter $\tau\in(0,1)$ represents the $\tau$-quantile of the random variable, $R$, which corresponds to the observed per-step reward from the MDP.

We can see from Equation (C.1) that by optimizing $b$, we end up with the reward VaR, which then turns the entire equation into an expectation (i.e., Equation (C.1b)) that we can then optimize using regular average-reward MDP solution methods. Existing MDP-based CVaR optimization methods typically formulate this problem as a bi-level optimization with an augmented state-space that includes an estimate of VaR, $b$ (see Equation (11)), thereby increasing computational costs.

With the RED RL framework however, we can circumvent both of these computational challenges by turning the optimization of $b$ into a subtask. In particular, we can see that if we treat the expression inside the expectation in Equation (C.1) as our subtask function, $f$ (see Definition 4.1), then we have a valid subtask function where the subtask, $b$ (an estimate of VaR), is independent of the observed reward (denoted here by $R$), thereby satisfying the definition for a subtask.

However, we cannot directly apply the RED RL framework to Equation (C.1) because Equation (C.1b) only holds for the actual VaR value, and so if we directly optimize the expectation in Equation (C.1b), we may not recover the actual VaR and CVaR values (i.e., there may be multiple solutions to Equation (C.1b), but we only care about the solution where $b=$VaR). Hence, we need to modify Equation (C.1b) to account for the fact that the expectation only holds when $b=$VaR.

It turns out that we can make the appropriate modification to Equation (C.1b) by leveraging a concept from quantile regression []. Quantile regression refers to the process of estimating a predetermined quantile of a probability distribution from samples. More specifically, let $\tau\in(0,1)$ be the $\tau$th quantile (or percentile) that we are trying to estimate from probability distribution $w$. Hence, the value that we are interested in estimating is $F_{w}^{-1}(\tau)$. Quantile regression maintains an estimate, $\theta$, of this value, and updates the estimate based on samples drawn from $w$ (i.e., $y\sim w$) as follows:

$$ $\theta\xleftarrow{}\theta+\eta_{\theta}(\tau-\mathds{1}_{\{y<\theta\}}),$ (C.2) $$

where $\eta_{\theta}$ is the step size for the update. The estimate for $\theta$ will continue to adjust until the equilibrium point, $\theta^{*}$, which corresponds to $F_{w}^{-1}(\tau)$, is reached. In other words, we have:

$$ $\displaystyle 0$ $\displaystyle=\mathbb{E}[(\tau-\mathds{1}_{\{y<\theta^{*}\}})]$ (C.3a) $\displaystyle=\tau-\mathbb{E}[\mathds{1}_{\{y<\theta^{*}\}})]$ (C.3b) $\displaystyle=\tau-\mathbb{P}(y<\theta^{*})$ (C.3c) $\displaystyle\implies\theta^{*}$ $\displaystyle=F_{w}^{-1}(\tau).$ (C.3d) $$

Equivalently, we also have:

$$ $\displaystyle 0$ $\displaystyle=\mathbb{E}[((1-\tau)-\mathds{1}_{\{y\geq\theta^{*}\}})]$ (C.4a) $\displaystyle=(1-\tau)-\mathbb{E}[\mathds{1}_{\{y\geq\theta^{*}\}})]$ (C.4b) $\displaystyle=(1-\tau)-\mathbb{P}(y\geq\theta^{*})$ (C.4c) $\displaystyle\implies\theta^{*}$ $\displaystyle=F_{w}^{-1}(\tau).$ (C.4d) $$

Hence, we can modify Equation (C.1) as follows:

$$ $\displaystyle\text{CVaR}_{\tau}(R)$ $\displaystyle=\max_{b\in\mathbb{R}}\mathbb{E}[b-\frac{1}{\tau}(b-R)^{+}]$ (C.5a) $\displaystyle=\mathbb{E}[\text{VaR}_{\tau}(R)-\frac{1}{\tau}(\text{VaR}_{\tau} (R)-R)^{+}]$ (C.5b) $\displaystyle=\mathbb{E}[\text{VaR}_{\tau}(R)-\frac{1}{\tau}(\text{VaR}_{\tau} (R)-R)^{+}]-0-0$ (C.5c) $\displaystyle=\mathbb{E}[\text{VaR}_{\tau}(R)-\frac{1}{\tau}(\text{VaR}_{\tau} (R)-R)^{+}]-a_{1}0-a_{2}0$ (C.5d) $\displaystyle\begin{split}&=\mathbb{E}[\text{VaR}_{\tau}(R)-\frac{1}{\tau}( \text{VaR}_{\tau}(R)-R)^{+}]-a_{1}\mathbb{E}[(\tau-\mathds{1}_{\{R<\text{VaR}_ {\tau}(R)\}})]\,\ldots\\ &\quad-a_{2}\mathbb{E}[((1-\tau)-\mathds{1}_{\{R\geq\text{VaR}_{\tau}(R)\}})] \\ \end{split}$ (C.5e) $\displaystyle\begin{split}&=\mathbb{E}[\text{VaR}_{\tau}(R)-\frac{1}{\tau}( \text{VaR}_{\tau}(R)-R)^{+}-a_{1}\left(\tau-\mathds{1}_{\{R<\text{VaR}_{\tau}( R)\}}\right)\ldots\\ &\quad-a_{2}\left((1-\tau)-\mathds{1}_{\{R\geq\text{VaR}_{\tau}(R)\}}\right)], \end{split}$ (C.5f) $$

where, $a_{1}$ and $a_{2}$ are positive scalars. Empirically, we found that setting $a_{1}=1.0$ and $a_{2}=(1-\tau$) yielded good results. Here, we have essentially added a ‘penalty’ into the expectation for having a VaR estimate that does not equal the actual VaR value. With this, we have narrowed the set of possible solutions that maximize the expectation, to those that have an acceptable VaR estimate.

We can now optimize (or to be more precise, maximize) the expectation in Equation (C.5f) using the RED RL framework, where VaR is the subtask that we want to optimize simultaneously. We can see that when the VaR estimate is equal to the actual VaR value, the quantile regression-inspired terms in Equation (C.5f) become zero. This helps maximize the expectation while recovering the VaR value, which, by definition, maximizes the CVaR value, all without having to add the VaR value to the state-space, or having to perform an explicit bi-level optimization.

We now have everything we need to apply the RED RL framework, where the subtask function, $f$, corresponds to the expression inside the expectation in Equation (C.5f) (and where $R$ corresponds to the observed per-step reward). With some algebra, the resulting reward-extended TD error update (see Equation (16)) for the subtask, VaR, is as follows:

$$ $\text{VaR}_{t+1}=\begin{cases}\text{VaR}_{t}-\eta\alpha\delta_{t},&R_{t}\geq \text{VaR}_{t}\\ \text{VaR}_{t}+\eta\alpha(\frac{\tau}{1-\tau})\delta_{t}&R_{t}<\text{VaR}_{t} \end{cases},$ (C.6) $$

where $\delta_{t}$ is the TD error, $\eta\alpha$ is the step size, and $\tau$ is the CVaR parameter.

As such, we have now derived all of the components of the RED CVaR learning algorithms. The full algorithms are included at the end of this Appendix. In terms of the RED CVaR learning algorithms, Algorithm 5 corresponds to the RED CVaR Q-learning algorithm used in the red-pill blue-pill experiment, and Algorithm 7 corresponds to the RED CVaR Actor-Critic algorithm used in the inverted pendulum experiment. In terms of the Differential learning algorithms used for comparison, Algorithm 6 corresponds to the Differential Q-learning algorithm used in the red-pill blue-pill experiment, and Algorithm 8 corresponds to the Differential Actor-Critic algorithm used in the inverted pendulum experiment. We describe both experiments in detail in the subsequent sections.

### C.2 Red-pill blue-pill experiment

In the first experiment, we consider a two-state environment that we created for the purposes of testing our algorithms. It is called the red-pill blue-pill environment (see Appendix D), where at every time step an agent can take either a red pill, which takes them to the ‘red world’ state, or a blue pill, which takes them to the ‘blue world’ state. Each state has its own characteristic reward distribution, and in this case, the red world state has a reward distribution with a lower (worse) mean but higher (better) CVaR compared to the blue world state. Hence, we would expect the regular Differential Q-learning algorithm to learn a policy that prefers to stay in the blue world, and that the RED CVaR Q-learning algorithm learns a policy that prefers to stay in the red world. This task is illustrated in Fig. 3a).

For this experiment, we ran both algorithms using various combinations of step sizes for each algorithm. We used an $\epsilon$-greedy policy with a fixed epsilon of $0.1$, and a CVaR parameter, $\tau$, of $0.25$. We set all initial guesses to zero. We ran the algorithms for 100k time steps.

For the Differential Q-learning algorithm, we tested every combination of the value function step size, $\alpha\in\{\text{2e-1, 2e-2, 2e-3, 2e-4},1/n\}$ (where $1/n$ refers to a step size sequence that decreases the step size according to the time step, $n$), with the average-reward step size, $\eta\alpha$, where $\eta\in\{\text{1e-4, 1e-3, 1e-2, 1e-1, 1.0, 2.0}\}$, for a total of 30 unique combinations. Each combination was run 25 times using different random seeds, and the results were averaged across the runs. The resulting (averaged) average-reward over the last 1,000 time steps is displayed in Fig. C.1. As shown in the figure, a value function step size of 2e-4 and an average-reward $\eta$ of 1.0 resulted in the highest average-reward in the final 1,000 time steps in the red-pill blue-pill task. These are the parameters used to generate the results displayed in Fig. 4a). These parameters had a coefficient of variation with a magnitude of 2.33e-2 across the various random seed runs.

Figure: Figure C.1: Step size tuning results for the red-pill blue-pill task when using the Differential Q-learning algorithm. The average-reward in the final 1,000 steps is displayed for various combinations of value function and average-reward step sizes.
Refer to caption: extracted/5965996/images/tuning_2.png

For the RED CVaR Q-learning algorithm, we tested every combination of the value function step size, $\alpha\in\{\text{2e-1, 2e-2, 2e-3, 2e-4},1/n\}$, with the average-reward (in this case CVaR) $\eta\in\{\text{1e-4, 1e-3, 1e-2, 1e-1, 1.0, 2.0}\}$, and the VaR $\eta\in\{\text{1e-4, 1e-3, 1e-2, 1e-1, 1.0, 2.0}\}$, for a total of 180 unique combinations. Each combination was run 25 times using different random seeds, and the results were averaged across the runs. The resulting (averaged) reward CVaR over the last 1,000 time steps is displayed in Fig. C.2. As shown in the figure, combinations with larger step sizes converged to the optimal policy within the 100k time steps, and combinations with smaller step sizes did not (see Section C.4 for more discussion on this point). A value function step size of 2e-2, an average-reward (CVaR) $\eta$ of 1e-2, and a VaR $\eta$ of 1e-2 were used to generate the results displayed in Fig. 4a) and Fig. 5. These parameters had a coefficient of variation with a magnitude of 6.31e-3 across the various random seed runs.

Figure: Figure C.2: Step size tuning results for the red-pill blue-pill task when using the RED CVaR Q-learning algorithm. Each plot represents a different $\eta_{{}_{\text{VaR}}}$ used: a) 2e-4; b) 2e-3; c) 2e-2; d) 2e-1; e) 1.0; f) 2.0. Within each plot, the reward CVaR in the final 1,000 steps is displayed for various combinations of value function and average-reward (in this case CVaR) step sizes.
Refer to caption: extracted/5965996/images/tuning_1.png

Fig. C.3a) shows the VaR and CVaR estimates as learning progresses when using the RED CVaR Q-learning algorithm with the same step sizes used in Figures 4a) and 5. We see that the resulting VaR and CVaR estimates generally track with what one would expect (similar values, with the VaR value being slightly larger than the CVaR value). We can see however that these estimates do not correspond to the actual VaR and CVaR values induced by the policy (as shown in Fig. 4a)). This is because, as previously mentioned, the solutions to the average-reward MDP Bellman equations (Equations (4), (5)), which in this case include the VaR and CVaR estimates, are only correct up to a constant. For comparison, we hard-coded the true VaR value and re-ran the same experiment, and found that the agent still converged to the correct policy, this time with a CVaR estimate that matched the actual CVaR value. Fig. C.3b) shows the results of this hard-coded VaR run.

Figure: Figure C.3: The VaR and CVaR estimates as learning progresses when using the RED CVaR Q-learning algorithm: a) as per usual, and b) when hard-coding the VaR estimate to the true VaR.
Refer to caption: extracted/5965996/images/tuning_4.png

### C.3 Inverted pendulum experiment

In the second experiment, we consider the well-known inverted pendulum task, where an agent learns how to optimally balance an inverted pendulum. We chose this task because it provides us with opportunity to test our algorithm in an environment where: 1) we must use function approximation (given the large state and action spaces), and 2) where the policy for the optimal average-reward and the policy for the optimal reward CVaR is the same policy (i.e., the policy that best balances the pendulum will yield a stationary reward distribution with both the optimal average-reward and reward CVaR). This hence allows us to directly compare the performance of our RED algorithms to the regular Differential learning algorithms, as well as to gauge how function approximation affects the performance of our algorithms. For this task, we utilized a simple actor-critic architecture [] as this allowed us to compare the performance of the (non-tabular) RED TD-learning algorithm with a (non-tabular) Differential TD-learning algorithm. This task is illustrated in Fig. 3b).

For this experiment, we ran both algorithms using various combinations of step sizes for each algorithm. We used a fixed CVaR parameter, $\tau$, of $0.1$. We set all initial guesses to zero. We ran the algorithms for 100k time steps. For simplicity, we used tile coding [] for both the value function and policy parameterizations, where we parameterized a softmax policy. For each parameterization, we used 32 tilings, each with 8 X 8 tiles. By using a linear function approximator (i.e., tile coding), the gradients for the value function and policy parameterizations can be simplified as follows:

$$ $\nabla\hat{v}(s,\boldsymbol{w})=\boldsymbol{x}(s),$ (C.7) $$

$$ $\nabla\text{ln}\pi(a\mid s,\boldsymbol{\theta})=\boldsymbol{x}_{h}(s,a)-\sum_{ \xi\in\mathcal{A}}\pi(\xi\mid s,\boldsymbol{\theta})\boldsymbol{x}_{h}(s,\xi),$ (C.8) $$

where $s\in\mathcal{S}$, $a\in\mathcal{A}$, $\boldsymbol{x}(s)$ is the state feature vector, and $\boldsymbol{x}_{h}(s,a)$ is the softmax preference vector.

For the RED CVaR Actor-Critic algorithm, we tested every combination of the value function step size, $\alpha\in\{\text{2e-2, 2e-3, 2e-4},1/n\}$ (where $1/n$ refers to a step size sequence that decreases the step size according to the time step, $n$), with $\eta$’s for the average-reward, VaR, and policy step sizes, $\eta\alpha$, where $\eta\in\{\text{1e-3, 1e-2, 1e-1, 1.0, 2.0}\}$, for a total of 500 unique combinations. Each combination was run 10 times using different random seeds, and the results were averaged across the runs. The resulting (averaged) reward CVaR over the last 1,000 time steps is displayed in Fig. C.4a) and the resulting (averaged) average-reward over the last 1,000 time steps is displayed in Fig. C.4b). As shown in the figure, most combinations allow the algorithm to converge to the optimal policy that balances the pendulum (as indicated by a reward CVaR and average-reward of zero). A value function step size of 2e-3, a policy $\eta$ of 1.0, an average-reward (CVaR) $\eta$ of 1e-2, and a VaR $\eta$ of 1e-2 were used to generate the results displayed in Fig. 4b). These parameters had a coefficient of variation with a magnitude of 2.85 across the various random seed runs.

For the Differential Actor-Critic algorithm, we tested every combination of the value function step size, $\alpha\in\{\text{2e-2, 2e-3, 2e-4},1/n\}$, with $\eta$’s for the average-reward and policy step sizes, $\eta\alpha$, where $\eta\in\{\text{1e-3, 1e-2, 1e-1, 1.0, 2.0}\}$, for a total of 100 unique combinations. Each combination was run 10 times using different random seeds, and the results were averaged across the runs. The resulting (averaged) reward CVaR over the last 1,000 time steps is displayed in Fig. C.4c) and the resulting (averaged) average-reward over the last 1,000 time steps is displayed in Fig. C.4d). As shown in the figure, most combinations allow the algorithm to converge to the optimal policy that balances the pendulum. A value function step size of 2e-3, a policy $\eta$ of 1.0, and an average-reward $\eta$ of 1e-3 were used to generate the results displayed in Fig. 4b). These parameters had a coefficient of variation with a magnitude of 2.16e-1 across the various random seed runs.

Figure: Figure C.4: Step size tuning results for the inverted pendulum task when using the RED CVaR TD-learning and Differential TD-learning algorithms (through an actor-critic architecture). Each plot shows a histogram of either the reward CVaR or average-reward in the last 1,000 steps. More specifically, the histograms show: a) the reward CVaR when using the RED algorithm; b) the average-reward when using the RED algorithm; c) the reward CVaR when using the Differential algorithm; d) the average-reward when using the Differential algorithm.
Refer to caption: extracted/5965996/images/tuning_3.png

Fig. C.5a) shows the VaR and CVaR estimates as learning progresses when using the RED CVaR Actor-Critic algorithm with the same step sizes used in Fig. 4b). We see that the resulting VaR and CVaR estimates generally track with what one would expect (similar values, with the VaR value being slightly larger than the CVaR value). We can see however that these estimates do not correspond to the actual VaR and CVaR values induced by the policy (as shown in Fig. 4b)). This is because, as previously mentioned, the solutions to the average-reward MDP Bellman equations (Equations (4), (5)), which in this case include the VaR and CVaR estimates, are only correct up to a constant. For comparison, we hard-coded the true VaR value and re-ran the same experiment, and found that the agent still converged to the correct policy, this time with a CVaR estimate that more closely matched the actual CVaR value (note that in the inverted pendulum environment, rewards are capped at zero). Fig. C.5b) shows the results of this hard-coded VaR run.

Figure: Figure C.5: The VaR and CVaR estimates as learning progresses when using the RED CVaR TD-learning algorithm (through an actor-critic architecture): a) as per usual, and b) when hard-coding the VaR estimate to the true VaR value. Note that in the inverted pendulum environment, rewards are capped at zero.
Refer to caption: extracted/5965996/images/tuning_5.png

### C.4 Commentary on experimental results

Red-Pill Blue-Pill: In the red-pill blue-pill task, we can see from Fig. C.1 that for combinations with large step sizes, the RED CVaR Q-learning algorithm was able to successfully learn a policy, within the 100k time steps, that prioritizes maximizing the reward CVaR over the average-reward, thereby achieving a sort of risk-awareness. However, for combinations with smaller step sizes, particularly for low VaR $\eta$’s, the algorithm did not converge in the allotted training period. We re-ran some of the combinations with constant step sizes for longer training periods, and found that the algorithm eventually converged to the risk-aware policy given enough training time. For combinations with the $1/n$ step size, we found that if the other step sizes in the combination were sufficiently small, the algorithm would not converge to the correct policy (even with more training time). This suggests that a more slowly-decreasing step size sequence should be used instead so that the algorithm has more time to find the correct policy before the step sizes in the sequence become too small.

Inverted Pendulum: In the inverted pendulum task, we can see from Fig. C.4 that both algorithms achieved similar performance, as shown by the similar histograms for both the reward CVaR and average-reward during the final 1,000 time steps. These results suggest that both algorithms converged to the same set of (sometimes sub-optimal) policies, as expected.

Overall: In both experiments, we can see that with proper hyperparameter tuning, the RED CVaR algorithms were able to consistently and reliably find the optimal CVaR policy. The VaR and CVaR estimates generally tracked with what one would expect (similar values, with the VaR value being slightly larger than the CVaR value). However, these estimates were not always the same as the actual VaR and CVaR values induced by the policy because the solutions to the average-reward MDP Bellman equations are only correct up to a constant. This is typically not a concern, given that the relative ordering of the policies is usually what is of interest.

### C.5 Compute time and resources

For the red-pill blue-pill hyperparameter tuning, each case (which encompassed a specific combination of step sizes) took roughly 1 minute (total) to compute all 25 random seed runs for the case on a single CPU, for an approximate total of 4 CPU hours. For the inverted pendulum hyperparameter tuning, each case took roughly 5 minutes (total) to compute all 10 random seed runs for the case on a single CPU, for an approximate total of 50 CPU hours.

### C.6 Algorithms

Below is the pseudocode for the algorithms used in the experiments discussed in this Appendix.

Figure: Algorithm 5 RED CVaR Q-Learning (Tabular)

Figure: Algorithm 6 Differential Q-Learning (Tabular)

Figure: Algorithm 7 RED CVaR Actor-Critic

Figure: Algorithm 8 Differential Actor-Critic

## Appendix D Red-pill blue-pill environment

This Appendix contains the code for the red-pill blue-pill environment introduced in this work. The environment consists of a two-state MDP, where at every time step an agent can take either a red pill, which takes them to the ‘red world’ state, or a blue pill, which takes them to the ‘blue world’ state. Each state has its own characteristic reward distribution, and in this case, the red world state has a reward distribution with a lower (worse) mean but higher (better) CVaR compared to the blue world state. More specifically, the red world state reward distribution is characterized as a gaussian distribution with a mean of $-0.7$ and a standard deviation of $0.05$. The blue world state is characterized by a mixture of two gaussian distributions with means of $-1.0$ and $-0.2$, and standard deviations of $0.05$. We assume all rewards are non-positive.

The Python code for the environment is provided below:

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See above.
soundness: 3
strengths: The paper studies an interesting problem in average-reward RL, which leverages a structural property that is specific to average-reward MDPs. The introduced framework appears interesting in its generic form, although its presentation in the paper is done in a rather high and abstract level. I found its application to CVaR RL quite interesting. In addition, that it removes the need to solve bi-level optimization problems explicitly is definitely a plus.  

The paper is mostly well-organized and well-written. I have a couple of minor comments about writing and organization that I defer until the next section. Whenever applicable, the paper uses some figures to illustrate some concept, which proved quite helpful. 

The paper includes numerical experiments, which is a positive aspect. The two domains used for the experiments sound interesting and relevant to showcase the framework.
summary: This paper studies a class of average-reward reinforcement learning problems, which includes risk-sensitive RL as special case.  The main contribution is a new framework called Reward-Extended Differential (RED) RL, which leverages structural properties of average-reward RL. RED RL can be used to devise RL algorithms for a rather broad range of objectives admitting some notion called “subtask”. In particular, the paper showcases the efficacy of this framework in the design of risk-averse RL algorithms under the CVaR risk measure, and this appears to be main motivation behind RED RL. The key benefit of the new framework here would be to avoid bi-level optimization or state-space augmentation that appear in the existing RL algorithms under CVaR criterion.
weaknesses: Main Comments:
-
- One main comment is regarding the assumption. In view of statements in line 123-124, it appears to me that effectively a unichain assumption is made both for prediction and control. 

- As a weak aspect, the presented framework only is shown to enjoy asymptotic convergence (in the tabular case). 

- Regarding CVaR RL, use of an augmented state-space is mentioned as a standard technique. Of course, it is clear that we lack interest in extending state-space – especially if there is some workaround – for the classical performance bounds that deteriorate as the size of state-space grows. However, it is worth remarking that an “augmented but highly structured” state-space is not necessarily a weak aspect if one could leverage the underlying structure. Could you explain whether this is the case for CVaR RL? 

- In Section 5, Equation 19: could you clarify what the choice of function $f$ is.

- As a general comment, I wonder whether RED performs simultaneous learning of multiple subtasks without any sacrifice? If not, it is not highlighted enough in the paper (or maybe I miss something).

- Subtask may bring some confusion because of its use as a standard terminology in hierarchical RL terminology. Also, I do not think that this choice of naming effectively reflects what it actually serves. Other candidates? 

- I found the literature review part rather week. Admittedly, there is a rarity of prior work dealing with learning multiple goals/objectives in average-reward MDPs. However, in other MDPs settings and bandits – that are obviously more straightforward to analyze – there might exist a relatively richer literature. Further, one key contribution of the paper falls into the realm of risk-sensitive RL. It is therefore expected to see a better coverage of the related literature (and for discounted and episodic settings). 

- The preliminary on average-reward MDPs and RL is rather long. Despite less work on them comparatively, they are standard settings and notions for a venue such as ICLR. I suggest Section 3.1 to be compressed to that the space in the main text could be used for more novel aspects. 

Minor Comments:
- 
- Figures are not readable. 

Typos:
-
- Line 84: builds off of Wan et al. ==> Did you mean “builds on Wan et al.”?
- Line 61: in the Appendix ==> I think it is more correct to use “in Appendix” or “in the appendix”. 
- Line 105: $S$ is a finite set of states, $A$ is … ==> $\mathcal S$ is …, $\mathcal A$ is …

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Do we know the proposed algorithm updating VaR and CVaR simultaneously would converge to the optimal fixed point, not any other fixed point?

(a) The quantile regression stochastic approximation from equation (C.2) provides a quantile estimate which may not be unique for discrete random variable, VaR is only an element of quantile which is not an elicitable risk measure (see [1]). Therefore, quantile regression may not converge to VaR, perhaps VaR is not necessary and any quantile estimate is sufficient? However, CVaR is also not elicitable which makes it unclear how stochastic approximation can approximate these values accurately. There may be an assumption missing for the subtask function $f$ to handle the nuances of the problem discussing here. 

(b) It is unclear why the VaR approximation in algorithm 7 is update with $\delta$ instead of the gradient of quantile (L1) loss update (C.2) (see [2]). Note that the gradient of L1 loss is a piecewise constant. 

(c) In Appendix C, the claim that "We can see that when the VaR estimate is equal to the actual VaR value, the quantile regression-inspired terms in Equation C.5f become zero" holds only for continuous distributions during policy evaluation. Furthermore, this is insufficient, the authors may need to demonstrate that, starting from any initial estimate, the VaR estimate converges to the actual VaR, and similarly, that the CVaR estimate converges to the actual CVaR. Even if convergence is achieved in policy evaluation, there is no proof validating this statement for the discrete case or for policy optimization.

References:

[1] Bellini, Fabio, and Valeria Bignozzi. "On elicitable risk measures." Quantitative Finance 15.5 (2015): 725-733.

[2] Shen, Yun, et al. "Risk-sensitive reinforcement learning." Neural computation 26.7 (2014): 1298-1328.
soundness: 2
strengths: (a) The abstract, introduction, and preliminaries on average reward reinforcement learning are well-written and clearly presented.

(b) The TD and Q-learning with stochastic approximation algorithms, along with Theorems 4.1–4.3, appear to be rigorously verified with proofs in Appendix B. These proofs effectively extend the results from [1, 2, 3] to the multi-subtasks setting proposed in this work.

References: 

[1] Wan, Yi, Abhishek Naik, and Richard S. Sutton. "Learning and planning in average-reward markov decision processes." International Conference on Machine Learning. PMLR, 2021.

[2] Vivek S Borkar. Asynchronous stochastic approximations. SIAM Journal on Control snd Optimization, 36(3):840–851, 1998.

[3] Vivek S Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Springer, 2009.
summary: This paper extends the risk-averse average-reward MDP framework from [1] and introduces a new approach called "Reward Extended Differential (RED)" for solving various subtasks (e.g., scalar prediction or control objectives) concurrently. Instead of using the observed reward $R$ directly, the TD error is defined using a modified reward $\tilde{R} = f(R,Z_1,Z_2 ...,Z_n)$ where $f$ is an invertible function mapping the observed reward and all subtasks to a modified reward $\tilde{R}$. The authors demonstrate their algorithm’s application to risk-averse (CVaR) decision-making in a fully online setting.

References: 

[1] Wan, Yi, Abhishek Naik, and Richard S. Sutton. "Learning and planning in average-reward markov decision processes." International Conference on Machine Learning. PMLR, 2021.
weaknesses: Despite the authors' in-depth understanding of stochastic approximation and model-free Q-learning proofs, the paper lacks sufficient validation regarding the extension to risk awareness in average reward MDPs.

(a) The paper demonstrates a limited engagement with prior work and foundational concepts in risk-averse CVaR MDPs. The authors inaccurately claim that “our work is the first to propose an MDP-based CVaR optimization algorithm that does not require an explicit bi-level optimization scheme or an augmented state-space.” However, several existing approaches such as dynamic risk-averse MDPs [1], risk-averse distributional RL [2, 3,11] and average-criteria CVaR [9] also avoid state-space augmentation and employ stationary Markov policies, similar to this work. Furthermore, the proposed algorithm still seems to be bilevel as it aim to optimize for CVaR but update the VaR estimate at every level. Moreover the author mentioned that "the CVaR that we aim to optimize most closely matches the static category", restricting to stationary Markov policies can impair both the optimality and interpretability of static CVaR MDPs (see [4, 5, 6, 7]), since the sum over $t \in 1:n$ for average criteria is outside of the CVaR operator, this is closer to the dynamic category where optimal deterministic stationary policy exist (see Theorem 1 of [9]). Additionally, the authors overlook related works [8] applies a similar TD update and [10] consider time-consistent policies set. It should be noted that "notable works such as [6]" describe in related work section, are known to be sub-optimal for policy optimization (see [7]). For this reason, augmented state-space primal methods with bi-level optimization, as in static CVaR MDP algorithms [4, 5, 9], are generally preferred.

(b) The CVaR analysis in Appendix C.1 is focused solely on evaluation, leaving out an analysis for policy optimization claim "We can now optimize the expectation in Equation C.5f using the RED RL framework". Additionally, the average criterion CVaR objective function itself is not explicitly presented in the paper. Sections 4 and 5 feel somewhat disconnected; providing a clearer explanation to link these sections, along with an explicit proof that the proposed algorithm can optimize the CVaR objective, would significantly strengthen the paper’s claims regarding risk-aware reinforcement learning in average reward MDPs.

(c) Limited empirical results: The results in Section 5 do not demonstrate that the proposed algorithm effectively optimizes the desired CVaR risk level. The evaluation would be more convincing if the authors trained the algorithm across multiple distinct CVaR risk levels (e.g. $\tau \in [0.01,0.05,0.1,0.5,1]$), and subsequently assessed performance by calculating the CVaR of the average reward over the final $n$ steps for each risk level $\tau' \in [0.01,0.05,0.1,0.5,1]$. Ideally, the maximum performance at each evaluated risk level should correspond to the training run specifically conducted at that CVaR risk level, reinforcing that the algorithm correctly optimizes for the specified risk. Furthermore, comparing the proposed algorithm’s performance with other approaches [4,9,11] under an average reward criterion could also provide a clearer benchmark for its effectiveness.

(d) The claim to “learn a policy that optimized the CVaR value without using an explicit bi-level optimization scheme or an augmented state-space, thereby alleviating some of the computational challenges” is not substantiated. This claim would be more convincing if the authors compared the computational complexity or running time of the proposed method with that of the algorithm proposed in [9].

References: 

[1] Ruszczyński, Andrzej. "Risk-averse dynamic programming for Markov decision processes." Mathematical programming 125 (2010): 235-261.

[2] Keramati, Ramtin, et al. "Being optimistic to be conservative: Quickly learning a CVaR policy." Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.

[3] Dabney, Will, et al. "Implicit quantile networks for distributional reinforcement learning." International conference on machine learning. PMLR, 2018.

[4] Nicole Bauerle and Jonathan Ott. Markov Decision Processes with Average-Value-at-Risk criteria. Mathematical Methods of Operations Research, 74(3):361–379, 2011.

[5] Nicole Bauerle and Alexander Glauner. Minimizing spectral risk measures applied to Markov decision processes. Mathematical Methods of Operations Research, 94(1):35–69, 2021.

[6] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision making: a CVaR optimization approach. In Advances in neural information processing systems 28, 2015.

[7] Hau, Jia Lin, et al. "On dynamic programming decompositions of static risk measures in Markov decision processes." Advances in Neural Information Processing Systems 36 (2024).

[8] Stanko, Silvestr, and Karel Macek. "Risk-averse Distributional Reinforcement Learning: A CVaR Optimization Approach." IJCCI. 2019.

[9] Xia, Li, Luyao Zhang, and Peter W. Glynn. "Risk‐sensitive Markov decision processes with long‐run CVaR criterion." Production and Operations Management 32.12 (2023): 4049-4067.

[10] Miller, Christopher W., and Insoon Yang. "Optimal control of conditional value-at-risk in continuous time." SIAM Journal on Control and Optimization 55.2 (2017): 856-884.

[11] Lim, Shiau Hong, and Ilyas Malik. "Distributional reinforcement learning for risk-sensitive policies." Advances in Neural Information Processing Systems 35 (2022): 30977-30989.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: I encourage the authors to account for previous reviews' comments and suggestions and update their paper accordingly.
soundness: 2
strengths: - The paper is easy to read, and the writing skills are good.
- I am unaware of previous work that proposed CVaR optimization for the average reward criterion, so this is original (as far as I can tell).
summary: This paper focuses on the infinite horizon average criterion, to learn CVaR return without bi-level optimization. Indeed, CVaR-MDPs i.e., MDPs under CVaR objective, require solving an optimization problem at each policy evaluation step. By switching to the CVaR of the average reward (instead of discounted), the authors introduce RED-CVaR, a TD-type algorithm that avoids the inner optimization problem. Convergence results are provided under standard assumption. The approach is validated on a two-state MDP and inverted pendulum.
weaknesses: I reviewed this paper for another venue where reviewers voted for rejection unanimously. 
There have not been any substantial updates since that submission, so my concerns apply to this one. I copy below the most critical concerns I had then: 

- Even in the risk-neutral case, the average reward criterion has some analytical advantages. Notably, [2] focuses on that same criterion rather than the discounted one. As a side comment, I am unaware of any provably convergent AC algorithms for the risk-neutral discounted return. In that respect, it does not surprise me that the same holds for risk-sensitive MDPs, which questions the significance of this work.
- Another missing related work is [5], which considers infinite horizon average reward but with entropic risk instead of CVaR
A discussion on the nature of the risk considered in this work is missing: is it nested or static? It looks static, i.e., the objective is $\text{CVaR}(\bar{r}_{\pi})$, not nested, see [3, 4]. Therefore, time-consistency issues may arise and if not, they should be discussed. On the other hand, the nested formulation enables doing DP but lacks interpretability.
- The initial claims in Sec 2.1 are incorrect: average criteria have been extensively studied already in the 60-s with Howard and Blackwell. In particular, the Blackwell optimality criterion bridges the gap between discounted and average returns. See Chaps 8-9 of [1].
Eqs (4)-(5) are called Poisson equations, see [2].
- In the risk-neutral case, [2] do function approximation on the average reward setting. I think the same could be done for CVaR + function approximation.
- Def 4.1 is unclear. How does this definition translate to the max in Eq. (10) ?
- The statements of Thms. 4.1 and 4.2 are vague and should be formalized: what do they show? Why not focus on just one subtask as this is the case of CVaR optimization?
- Formal algorithm pseudo-codes should appear instead of a list of equations (17)
- The learning rates $\eta$, $\alpha$ are sometimes constant, sometimes time or even state-dependent.
- The convergence plots seem to show one run per experiment. How is the seed chosen? Is it random? Have the algorithms been run on more seeds? The authors are encouraged to plot error curves with mean±std.


Broadly speaking, the following concerns led to my grading:

- Some claims are inaccurate, including related works.
- The experiments are somewhat unclear and not very convincing.
- Although optimizing a CVaR-average return criterion is new, the theoretical contribution seems to be a simple adaptation of risk-neutral TD to CVaR-TD. In particular, explaining the analytical challenges encountered under risk-sensitive criteria would be helpful. In particular, why is the unichain assumption still necessary? I think this comes from the static nature of the CVaR -- I don't think the same assumption would be required/enough if CVaR here were nested.


*[1] Puterman, Martin L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. [2] Bhatnagar, Shalabh, et al. "Incremental natural actor-critic algorithms." Advances in neural information processing systems 20 (2007). [3] Hau, Jia Lin, Marek Petrik, and Mohammad Ghavamzadeh. "Entropic risk optimization in discounted MDPs." International Conference on Artificial Intelligence and Statistics. PMLR, 2023. [4] Shen, Yun, Wilhelm Stannat, and Klaus Obermayer. "Risk-sensitive Markov control processes." SIAM Journal on Control and Optimization 51.5 (2013): 3652-3672. [5] Murthy, Yashaswini, Mehrdad Moharrami, and R. Srikant. "Modified Policy Iteration for Exponential Cost Risk Sensitive MDPs." Learning for Dynamics and Control Conference. PMLR, 2023.*

---

confidence: 3
contribution: 3
initial_rating: 3
presentation: 2
questions: See weaknesses.
soundness: 1
strengths: The claimed contribution has sufficient novelty. However, I am not an expert in this area so I can not confirm if the claim is true.
summary: This paper proposes a way to optimizes the conditional value-at-risk (CVaR) risk measure of the average-reward rate in finite MDPs. The CVaR of a random variable $X$ with a parameter $\tau in (0, 1)$ is the expectation of the lower $\tau$ quantile of X. The key idea is to utilize a property of CVaR by Rockafellar and Uryasev (2000) --- the CVaR of X with a parameter $\tau$ is the expectation of a piece-wise linear function of X and the value-at-risk (VaR; the lower $\tau$ quantile of X). By estimating VaR separately and treating the output of this piece-wise function as a new reward, the paper proposes that CVaR can be estimated using an existing average-reward algorithm. The key advantage of this approach to estimate the CVaR of the reward rate is that it does not perform the bi-level optimization and does not augment the state space, whereas existing algorithms need to do one of them.
weaknesses: I have three concerns about this paper.

First, the writing of this paper is vague, making it hard to understand. For example, it is not clear why subtasks are introduced when the main goal is the CVaR problem, until Section 5. Even in Section 5, the authors didn't explain explicitly how these two ideas are related and how equation (19) was derived. Another example is the discussion about the literature. The paper only mentioned one work for estimating CVaR (Xia et al. 2023) in the average-reward setting. Is that the only work? In addition, was the paper's idea applied to other settings (discounted, episodic) before? If so, what are the differences? 

Yet, the major problem is that the derivation of the results in the paper seems to be problematic. Specifically, the step from 13a to 13b does not hold in general for piece-wise linear function f (the proof says that f is linear but Definition 4.1 says that f can be piece-wise linear and in order to be applicable to CVaR, f needs to be piece-wise linear). Similarly, 14a to 14b does not seem to hold.

Third, there are quite a few typos/incorrectness/weird statements of this paper. I list some of them here:
"Average-reward (or average-cost) MDPs were first studied in works such as Puterman (1994)." Puterman's book summarizes previous works. I don't think it's fair to say that these MDPs were "first studied in works such as Puterman (1994)". 
At the beginning of Section 3.1, discreet -> discrete, S -> \mathcal{S}, A -> \mathcal{A}.
Equation 1 depends on the start state S_0 while the l.h.s. shows that it is not.
"Such assumptions ensure that, for the induced Markov chain, ...". \mu_\pi here is the limiting distribution, instead of a stationary distribution. In addition, the limiting distribution does not exist for periodic Markov chains.
Max in equation (10) should be Sup. So does several other places in the paper. 
Definition 4.1 (ii) should be a property on the function f, instead of a property on the z_i, because z_i is just a scalar input of f, not a random variable.
Lower case letters r, s, s' are sometimes used as random variables and sometimes used as scalars.

Meta-review: This paper introduces a Reward Extended Differential (RED) approach for risk-averse AMDP that aims to handle multiple subtasks concurrently, by defining the TD error through a modified reward generated by the observed rewards and subtasks through an invertible function. They leverage a property of CVaR from Rockafellar and Uryasev and treat CVaR as the expectation of a piecewise linear function of a random variable and its Value-at-Risk and hence apply the RED method to optimize the risk-averse CVaR objective function. 

However, apart from the relatively minor concerns in the related work discussion, numerical experiments, the paper has a major technical issue in that the derivation 13a-13b and 14a-14b, which does not hold for nonlinear functions. Although after the revision, the authors modified this proof and make it specific to linear $f$. However, linear $f$ does not contain their main target (CVaR). They authors claim in a hand-waving style that the proof can be trivially extended to piece-wise linear function by applying it on each piece. However, this claim is wrong. In fact, piece-wise linear functions provide uniform approximation of continuous functions over compact set, the authors' claim would suggest their result to hold for arbitrary continuous functions, which is impossible. 

Based on this technical issue, we decide to reject this paper.

Decision: Reject