Risk-Sensitive Reinforcement Learning: a Martingale Approach to Reward Uncertainty

We provide in section 2 a novel, conceptually meaningful decomposition of the cumulative reward process that distinguishes between the different sources of randomness contained within it (chaotic and predictable, cf. discussion above). The key idea of the paper is to apply the Doob decomposition of a stochastic process to the cumulative reward process. We believe that this decomposition in itself is of interest in gaining a better understanding of the variability contained within the reward process.

We then introduce in section 3 a new definition of risk that exactly captures reward uncertainty risk, i.e. the risk related to its non-deterministic nature: the chaotic variation associated to the reward process (and to a risk measure).

We incorporate for the first time reward uncertainty risk into model-free value-function based and policy gradient algorithms: the related modified versions of some canonical RL algorithms, so-called Chaotic Mean-Variance algorithms (CMV), are presented in section 4. These algorithms are applied to grid world and portfolio optimization problems in section 5. Although the focus in the main text is on the chaotic mean-variance case, our analysis in section 3 allows for general risk measures and we discuss some of them in the supplementary, such as the chaotic CVaR and Sharpe ratio.

As mentioned above, we are interested in developing a general RL framework to account for reward uncertainty in learned policies. The example presented in this section aims at illustrating what could sometimes go wrong when taking variance as a measure of risk, as it is commonly the case in the risk-sensitive RL literature (cf. section 1.3). We consider the episodic toy example of $T$ timesteps where there are 2 states, 2 actions, and at each state transition the probability to reach either states is the same, i.e. $P(s_{0}=2)=P(s_{0}=1)=P(s_{t+1}=1|s_{t},a_{t})=P(s_{t+1}=2|s_{t},a_{t})=\frac{1}{2}$. If $s_{t}=1$, the reward obtained at $t+1$ is 2 if $a_{t}=1$ and $4+\sigma h_{t+1}$ if $a_{t}=2$; if $s_{t}=2$, the rewards obtained at $t+1$ are 10 if $a_{t}=1$ and $8+\sigma h_{t+1}$ if $a_{t}=2$, where $h_{t}$ are i.i.d. zero mean unit variance, and the noise $\sigma\geq 0$. Think for example as action $a_{t}=2$ as investing in a risky stock at time $t$ and getting the corresponding price change at time $t+1$. If $\pi_{i}$ is the policy that always selects action $i$, then $\pi_{1},\pi_{2}$ have the same expected cumulative reward of $6T$. We have plotted in figure 1 the rewards obtained for the 2 policies in each state.

It can be proved that if the noise $\sigma^{2}$ is small enough (cf. supplementary for a precise quantitative statement), policy $\pi_{1}$ will be established as less risky than $\pi_{2}$ according to the variance criterion. Nevertheless, we know that the cumulative reward earned using $\pi_{1}$ over $T$ timesteps is bounded from below by $2T$ with probability 1. On the other hand, since $\pi_{2}$ contains the noise term $h_{t}$, there is always a positive probability that the reward hits any arbitrarily low value. That is, $\pi_{2}$ leaves the agent with a component that could constitute a true risk for him, whereas $\pi_{1}$ doesn’t, but is still established as the most risky according to the variance criterion. Hence, the risky noise component is not detected: section 2 will establish that this risky component is in fact the martingale associated to the Doob decomposition of the cumulative reward process. On the other hand, the conceptual tool introduced in this paper, the chaotic variation, when applied to the mean-variance case, will lead to a risk penalty term of $0$ for $\pi_{1}$ and proportional to $\sigma^{2}$ for $\pi_{2}$ (cf. supplementary), i.e. exactly the desired outcome that the penalty term is proportional to reward uncertainty only.

Another observation is the following: if $\sigma=0$, rewards are deterministic and the obvious optimal policy is to simply take the best reward in each state, i.e. $a_{t}=2$ if $s_{t}=1$ and $a_{t}=1$ if $s_{t}=2$. This optimal strategy generates a variance over $T$ timesteps of $9T$, due to the switching between states. If one chooses the risk aversion coefficient in the mean-variance trade-off to be high enough, one will then choose not to execute that obvious optimal policy and rather execute policy $\pi_{2}$ as it generates a lower variance of $4T$ over $T$ timesteps. On the other hand, the chaotic variation, when applied to the mean-variance case, will lead to a risk penalty term of $0$ for all policies (since rewards are deterministic) and hence one will always choose the optimal policy, whatever the risk aversion coefficient is.

There exists an interesting and growing body of literature on the topic of risk-sensitive RL. Our work contrasts with the latter in that we focus on learning policies sensitive to the uncertain nature of the rewards whereas previous work apply risk criterion to the cumulative reward as a whole, and hence do not distinguish between the different sources of randomness contained in it. Previously studied algorithms can be split into those that (i) are value-function based (cf. value iteration and policy iteration), and (ii) employ policy gradient methods that update the policy parameters in the direction of the gradient of the risk-flavored performance metric. In category (i), we cite the work of Mihatsch & Neuneier, (2002) in which they transform TD increments with a function that is linear by parts, and Borkar, (2002), Borkar, (2005), Borkar, (2010) which focuses on the exponential utility function in an ergodic average-reward type setting. Work of category (ii) are more numerous, and can be split into those that use (Actor-Critic) and do not use (Monte Carlo) a specific representation of the value function, the former usually requiring TD-type updates of the value function. For large action/state spaces, one typically employs function approximation of the value function in the actor-critic setting, which introduces bias but improves variance. On the RL front, Prashanth & Fu, (2018) provides a thorough literature review. Some references are interested in the full distribution of the cumulative reward, cf. Morimura et al. , (2010a), Morimura et al. , (2010b), Bellemare et al. , (2017), Defourny et al. , (2008) while others focus on specific risk measures, e.g. CVaR Tamar, A., Glassner, Y., Manor, S., (2015), Chow et al. , (2018). Some authors define their own notion of risk with specific applications in mind, such as Geibel & Wysotzki, (2005) for which risks refers to the likelihood of reaching so-called "error states". Tamar et al. , (2015) provides a general methodology to handle all coherent risk measures.

The most-studied framework remains the variance-related one. Variance can be understood as the variance of the cumulative reward, or as the sum of variances of step-by-step rewards, cf. the work of Prashanth & Ghavamzadeh, (2016), Tamar et al. , (2016), Tamar et al. , (2012) (in a stochastic shortest path context), Prashanth & Ghavamzadeh, (2013). Sobel, MJ, (1982) was among the firsts to study the mean-variance case, and he explains why using variance as a measure of risk may cause problems, more specifically the inability to use policy iteration type algorithms due to the lack of monotonicity of the variance operator, while Mannor & Tsitsiklis, (2011) shows that these problems can be hard to solve. Tamar et al. , (2016) provides a methodology to estimate the variance of the cumulative reward via a TD-type approach.

We present below the Bellman equation in the chaotic mean-variance case $\mathcal{C}_{\bm{\rho^{\pi}}}[\mathcal{R}_{0}](s_{0})=V^{\mathbb{V}(\beta)}_{\pi}(s_{0})$, cf. definition 4. It will be used to formulate a chaotic mean-variance version of Q-Learning in the episodic case (section 4.2), as well as to study actor-critic algorithms and the average reward case (cf. supplementary). The proof of theorem 2 follows directly from the definition of $\left<\mathcal{R}_{t}^{chaos}\right>$ in proposition 1.

In particular, in the episodic case with $\gamma=1$, theorem 2 yields that the class of optimal policies associated to (1) coincides with that associated to the modified rewards $R^{\beta}$. In contrast to traditional TD-based methods such as $Q$-Learning, $R^{\beta}$ is not directly observable as it involves the term $\overline{R}(s_{t},a_{t})$ which will need to be estimated over the course of the algorithm.

In the episodic mean-variance case (with $\gamma=1$), theorem 2 allows us to derive a chaotic version of Q-learning, cf. algorithm 1 which is based on theorem 3. In the discounted reward setting, it is not possible to combine $Q_{\pi}$ and $Q^{\mathbb{V}(\beta)}_{\pi}$ (where $Q_{\pi}(s_{t},a_{t}):=\mathbb{E}_{\pi}[\mathcal{R}_{t}|s_{t},a_{t}]$), hence we cannot get a Q-Learning type algorithm. The convergence proof is discussed in the supplementary and consists of a minor modification of the proof of Dayan & Watkins, (1992) based on the fact that $\overline{R}_{t}(s,a)\to\overline{R}(s,a)$ as $t\to+\infty$ with probability 1 for every state-action pair $(s,a)$, where $\overline{R}_{t}(s,a)$ is defined in theorem 3. The average reward version of the algorithm is presented in the supplementary.

In this section we consider episodic Monte Carlo based algorithms that start with a parametric form $\pi_{\theta}$ for the policy and optimize equation (1) in the direction of the gradient with respect to $\theta$, hence aiming for local optima only. We make the following classical assumption in this section (Bhatnagar et al. , (2009)):

From equation (1), we need to compute unbiased estimates of $\nabla_{\theta}\mathbb{E}_{\pi_{\theta}}[\mathcal{R}_{0}|s_{0}]$ and $\nabla_{\theta}\mathcal{C}_{\bm{\rho^{{\pi_{\theta}}}}}[\mathcal{R}_{0}](s_{0})$. The former is the classical expected reward gradient. By definition 3, $\mathcal{C}_{\bm{\rho^{{\pi_{\theta}}}}}[\mathcal{R}_{0}](s_{0})$ consists in applying a risk measure to a mean zero martingale, which is usually simpler as we will see below in the mean-variance case $\mathcal{C}_{\bm{\rho^{{\pi_{\theta}}}}}[\mathcal{R}_{0}](s_{0})=V^{\mathbb{V}(\beta)}_{\pi_{\theta}}(s_{0})$ (cf. definition 4), and more importantly the work done in the literature for specific risk measures can be applied straightforwardly, e.g. Chow et al. , (2018) or Tamar, A., Glassner, Y., Manor, S., (2015) in the case of CVaR (however the risk measure in our case is applied to the chaotic reward process $\mathcal{R}_{t}^{chaos}$ only). From now on we focus on the mean-variance case of definition 4, but we present in the supplementary extensions to chaotic CVaR and Sharpe ratio.

Provided we know $\overline{R}(s,a)$, the gradient $\nabla_{\theta}V^{\mathbb{V}(\beta)}_{\pi_{\theta}}(s_{0})$ presents no specific difficulty and can be computed using the classical likelihood ratio technique by generating $B\geq 1$ episodes $s_{0}^{(b)}$, $a_{0}^{(b)}$, $R_{1}^{(b)}$, …, $s_{T_{b}-1}^{(b)}$, $a_{T_{b}-1}^{(b)}$, $R_{T_{b}}^{(b)}$, $b=1..B$, following $\pi_{\theta}$ and computing the unbiased Monte Carlo estimate:

The subtlety here is that we need to learn $\overline{R}(s,a)$ in the course of the algorithm. In the tabular case, using assumption 2, we are guaranteed that every state-action pair $(s,a)$ will be visited infinitely often and we can proceed as in the Q-Learning case (theorem 3) by updating the (conditional) average estimate $\widehat{R}(s,a)$ as iterations on $\theta$ are performed. By the strong law of large numbers, convergence of $\widehat{R}(s,a)$ to $\overline{R}(s,a)$ occurs with probability 1. Remark 1 still holds here: since the iteration on the sample average $\widehat{R}(s,a)$ is uncoupled from the one on $\theta$, we do not need a two-timescale algorithm to guarantee convergence. For each $b=1..B$ and $t=0..T_{b}$, if $s=s_{t}^{(b)}$ and $a=a_{t}^{(b)}$ we perform the updates:

Alternatively, if the state or action spaces are large, one may want to use a parametric approximation $\widehat{R}_{\psi}(s,a)$ of $\overline{R}(s,a)$ that will be updated in the course of the algorithm: this approach is presented in algorithm 2, where we use an experience replay table and fit $\widehat{R}_{\psi}$ using SGD. Proposition 2 quantifies the related gradient bias due to the use of this approximation (proof in supplementary). We present in algorithm 3 the Chaotic Mean-Variance version of REINFORCE, which uses either equation (LABEL:eqe1) or algorithm 2.

In order to derive Actor-Critic algorithms, the Bellman equations in theorem 2 can be used - as in the CMV-Q-Learning algorithm 1 - in order to adapt the work of e.g. Prashanth & Ghavamzadeh, (2016) (variance case) or Chow et al. , (2018) (CVaR case) in order to derive chaotic versions of their actor-critic algorithms. This extension is discussed in the supplementary.

We consider the episodic problem of a robot on a grid aiming at a goal. The state space consists of the 16 grid squares, and the action space consists in choosing to go East, West, North or South. Reaching the goal (resp. taking a step) gives a +1 (resp. -1) reward and negative rewards are positioned on the grid as seen on figure 2. When an action $a_{t}$ is chosen, there is a probability $p_{error}=50\%$ that the robot goes in a random direction. If the robot hits the extremity of the grid, it stays where it is. We train policies using the CMV-Q-Learning algorithm 1. In figure 2 we plot the path heatmap over $10^{5}$ rollout steps performed with the learned policy for various risk aversion coefficients $\beta$ (cf. details and additional experiments in supplementary). The higher $\beta$, the further away from the -20 reward the robot goes, as expected, as it prefers taking the -6 loss rather than walking next to the -20 reward and risking to encur the corresponding loss.

The second element that our algorithm gives is a risk heatmap, highlighting the most uncertain states, i.e. the states which yield the highest reward stochasticity/uncertainty (figure 2). We perform rollouts with the learned $\overline{R}(\cdot,\cdot)$ and policy $\pi^{*}_{\beta}$ and compute $\mathbb{E}_{\pi^{*}_{\beta}}[(R_{t+1}-\overline{R}(s,\pi^{*}_{\beta}(s)))^{2}|s_{t}=s]$ for every state $s$. In figure 2 we see that as expected, the heatmap highlights the states next to the -20 reward, and to a lesser intensity the states around the -6 rewards. To the best of our knowledge, only two other work study risk-sensitive Q-Learning algorithms: Mihatsch & Neuneier, (2002) and Shen et al. , (2014). Both transform the TD-increments by a non-linear function in order to obtain risk-sensitive behaviors. The former show that their algorithm converge to the worst-case optimality criterion as the risk parameter changes, hence in our specific example, we could obtain similar paths as in figure 2, but our algorithm, in addition to being the only one to focus on reward stochasticity only, additionally provides the risk heatmap discussed above, which quantifies the extent to which a given state yields uncertain rewards.

We consider the problem of investing in 2 financial assets. One is risk-free in the sense that investing a quantity $q^{RF}_{t}$ in the asset yields a deterministic reward $R^{RF}_{t+1}:=q^{RF}_{t}\mu(s_{t})$, where $\mu$ is the risk-free rate. The latter can be seen as the overnight rate from day $t$ to day $t+1$, which is known at the end of day $t$ when $q^{RF}_{t}$ is chosen. The other asset is risky (e.g. a stock) and yields an uncertain reward for a quantity $q^{R}_{t}$ of $R^{R}_{t+1}:=q^{R}_{t}(\mu(s_{t})+\sigma(s_{t})h_{t+1})$, where $(h_{t})$ are i.i.d. standard normal and $\sigma$ is referred to as volatility. We restrict $q^{RF}_{t},q^{R}_{t}$ to be nonnegative integers which sum is less than a total investment constraint $q_{max}$. The action is defined as $a_{t}:=(q^{RF}_{t},q^{R}_{t})$ and the reward $R_{t+1}:=R^{RF}_{t+1}+R^{R}_{t+1}$. In our experiments we take $q_{max}=5$, yielding $21$ possible actions. The state space consists of 3 states LowVol, HighVol and MediumVol defined as low volatility $\sigma$ (and low risk-free rate $\mu$), high volatility (and high risk-free rate $\mu$), as well as an intermediate state. The state transition matrix is designed such that the more we trade in the risky asset (i.e. the higher $q^{R}_{t}$), the more likely we are to reach a higher volatility state. We train the policy using CMV-REINFORCE algorithm 3 and its baseline (classical mean-variance), and use it to compute performance metrics over rollout episodes of $T$ timesteps. Details on training/numerical values used are presented in the supplementary.

We display in figure 3 the fraction of time the process has spent in each state, as well as the investment fraction in each asset (for rollout episodes). With $\beta=0$ and by design of the state transition matrix, both assets give the same expected reward $\mu$ but the policy is incentivized to trade in the risky asset rather than in the risk-free asset in order to reach the HighVol state, which gives the highest $\mu$. As $\beta$ increases, in the CMV case, the policy shifts towards trajectories which contain less reward uncertainty, which means investing in the risk-free asset which associated rewards are deterministic. The classical mean-variance case (baseline) penalizes not only the variability related to reward uncertainty but also the variability related to the switching of states appearing in both assets via the deterministic term $\mu(s_{t})$, hence as $\beta$ increases, the policy is incentivized to stop investing (cf. green line in figure 3 representing the uninvested budget $q_{max}-q^{RF}_{t}-q^{R}_{t}$), i.e. it stops taking advantage of the risk-free asset. The latter can also be seen in figure 4 where we plot for rollout episodes the cumulative reward mean and standard deviation as a function of $\beta$. In the mean-variance case the reward mean will eventually vanish as the policy will stop trading in both assets: by trying to make the standard deviation lower, it generates a counterintuitive behavior in that it stops taking advantage of the risk-free asset.