{'fraction_non_alphanumeric': 0.03142691090686011, 'fraction_numerical': 0.011322298039046861, 'mean_word_length': 4.59802385829618, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ACReL: Adversarial Conditional value-at-risk Reinforcement Learning

In the classical Reinforcement Learning (RL) setting, one aims to find a policy that maximizes its expected return. This objective may be inappropriate in safety-critical domains such as healthcare or autonomous driving, where intrinsic uncertainties due to stochastic policies and environment variability may lead to catastrophic failures. This can be addressed by using the Conditional-Value-at-Risk (CVaR) objective to instill risk-aversion in learned policies. In this paper, we propose Adversarial Cvar Reinforcement Learning (ACReL), a novel adversarial meta-algorithm to optimize the CVaR objective in RL. ACReL is based on a max-min between a policy player and a learned adversary that perturbs the policy player's state transitions given a finite budget. We prove that, the closer the players are to the game's equilibrium point, the closer the learned policy is to the CVaR-optimal one with a risk tolerance explicitly related to the adversary's budget. We provide a gradient-based training procedure to solve the proposed game by formulating it as a Stackelberg game, enabling the use of deep RL architectures and training algorithms. Empirical experiments show that ACReL matches a CVaR RL state-of-the-art baseline for retrieving CVaR optimal policies, while also benefiting from theoretical guarantees.


Introduction
Reinforcement Learning (RL) [Sutton et al., 1998] is a branch of machine learning where the learner (agent) must learn how to behave in an environment by trial and error. In the classical RL setting, the objective is to find agents that maximize their expected return. This expectation maximization objective has led to impressive successes in domains like videogames [Vinyals et al., 2019], board games  or content recommendation [Li et al., 2010]. However, in safety-critical domains like healthcare, autonomous driving or financial planning, some erroneous actions may lead to disastrous consequences. In healthcare for instance, an RL agent may be in charge of designing the shortest path to an organ for surgery. In this task, some paths may be shorter but at the same time may be risk endangering the patient as they are too close to an artery, a nerve or a critical region of the brain [Baek et al., 2018]. Automation in this context and other safety-critical domains can only come if the agent is able to successfully reach its goal while avoiding the most risky actions [Gottesman et al., 2019]. Therefore, the classical RL approach of naively maximizing the expected return is not appropriate in such scenarios.
This has motivated the community to design risk-sensitive agents trained to take into account the uncertainty over their return, with special attention on catastrophic events. This can be achieved by including a risk measure [Artzner et al., 1999] in the learning objective. A common risk measure is the Conditional Value-at-Risk (CVaR α ), defined as the expectation over the worst α-quantile of a distribution. Lowering the value of α increases the risk-aversion. The search for CVaR-optimal policies, usually referred to as CVaR RL, is typically achieved with distributional RL [Dabney et al., 2018, Keramati et al., 2020, Singh et al., 2020, Schubert et al., 2021. However, these strategies lack theoretical guarantees on convergence to risk-sensitive objectives [Dabney et al., 2018].
Inspired by how the game-theoretic perspective has helped advance other fields like Generative Adversarial Networks (GANs) [Berthelot et al., 2017, Goodfellow et al., 2020, we address the lack of CVaR RL strategies with theoretical optimality guarantees by borrowing tools from game theory. More precisely, we suggest that learning the CVaR optimal policy in a risk-averse RL setting can be cast as a max-min game [Neumann, 1928] between the RL agent and a learned adversary. In the resulting setting that we call Adversarial Cvar Reinforcement Learning (ACReL), a learning agent aiming at maximizing its reward collection is perturbed by an adversary, whose goal is to minimize the rewards obtained by the agent. Our contributions are the following: • we propose ACReL, a max-min game formulation of CVaR RL with learnable agent and adversarial policies; • we provide a theoretical analysis showing that the game equilibrium yields CVaR-optimal policies; • we provide a theoretical analysis of a gradient-based algorithm to solve the proposed game.
The rest of the paper is organized as follows. We first introduce the necessary background and notation (Section 2). We then formulate the ACReL setting alongside its relevant properties allowing to conduct a theoretical convergence analysis linking the game equilibrium point to a CVaR-optimal RL policy (Section 3). This leads us to consider a gradient-based algorithm leveraging the Stackelberg game formulation, for which we provide a theoretical convergence analysis (Section 4). We present empirical results showing that the proposed approach matches the performance of a state-of-the-art risk-sensitive baseline in finding CVaR-optimal RL policies (Section 5). Lastly, we provide an overview of the related work (Section 6).

Background and Notation
The most common RL problem formulation is under the Markov Decision Process (MDP) framework. An MDP is represented by a tuple S, A, P, R, γ , where S is the state space, A is the action space, P(·|s, a) is the transition kernel which governs the evolution of the system, R is the reward function for a given state-action pair, and γ ∈ [0, 1) is a discount factor. On each time step t, the learning agent evolving in the described environment observes the current state s t ∈ S, takes an action a t ∈ A, transitions in the next state s t+1 ∼ P(s t , a t ), and observes the associated reward r t+1 ∼ R(s t , a t , s t+1 ). The behavior of the agent is represented by a policy π(·|s) mapping any state s ∈ S to a probability distribution over actions, such that a t ∼ π(s t ).
Intuitively, the CVaR α [Z] can be viewed as the mean over the α-quantile worst values of Z. Since Z represents discounted returns in our case, the worst values of Z can be seen as the ones where most risk has been incurred. This last interpretation is particularly attractive, as it makes the CVaR α easy to understand for non-experts who might be involved in the design of any risk-sensitive model in safety-critical domains.
CVaR Reinforcement Learning To measure the level of risk associated with a policy π, the CVaR α measure (Eq. 2) can be applied to the discounted return J (π) (Eq. 1). Optimizing for this yields the CVaR RL objective This objective, which differs from the classical expectation maximization goal, can be viewed as finding a risk-sensitive policy. Indeed, by aiming for the optimal CVaR α return, the optimal policy π * is maximizing the expectation over the α-tail worst returns. Since the expectation is now taken over a small, disadvantageous subset of returns rather than over all of them, π * is more sensible towards avoiding the probability of large negative returns. In practice, this means that optimizing for the CVaR RL objective (Eq. 3) will produce policies that accept to reduce their expected performance, so long as it means they avoid catastrophic trajectories in return. In other words, they will reduce uncertainty at the expense of performance.

ACReL
Before diving into the details of the proposed adversarial game, let us first present the necessary assumption on the target MDP for the game to be applicable.
Assumption 1. State transitions P are stochastic, they can be accessed, and their non-zero values can be arbitrarily modified.
Stochasticity is required because it is precisely upon state transitions uncertainties that the adversary will be acting. State transitions must also be accessible to allow adversarial actions to be registered. The accessibility requirement, albeit more restrictive, is likely to be met in artificial environments over which the user has almost complete control, in the Sim2Real [Peng et al., 2018] context for instance. We however emphasize that accessibility is only needed to characterize the game's equilibrium as theoretically CVaR optimal. This means that our game framework may still be used in practice with different adversarial disturbances, only at the cost of losing the presented theoretical guarantees on the game's solution.

Game Setting
The goal is to learn a risk-sensitive policy with respect to the CVaR α risk measure. To achieve this, we leverage the perturbation model from  to design a max-min game where an agent tries to learn a policy π θ to maximize its return while an adversary tries to learn a perturbation policy ν ω that instead minimizes the agent's return, where θ and ω respectively denote the parameters of the agent and adversarial policies.
We note that, due to the time-inconsistent nature of CVaR in sequential problems [Gagne and Dayan, 2021], it is well known that the optimal policy π * for the CVaR RL objective can be history-dependent [Shapiro et al., 2014]. We hereby follow previous work on CVaR RL [Keramati et al., 2020, Dabney et al., 2018 and limit our analysis to stationary, history independent policies which can be suboptimal but typically achieve high CVaR nonetheless in practice.
The adversary Let P t = P(· | s t , a t ) denote time step transition dynamics given a trajectory τ = {(s t , a t , r t )} T t=1 performed by the agent, where T is the duration of the trajectory. At time step t, the adversary can access and perturb P t with a positive multiplicative probability perturbation δ t . This yields perturbed transitionsP t = P t • δ t , where • denotes the Hadamard (element-wise) product. To be admissible, a perturbation δ t must generate a valid transition kernel, i.e.P t (s) ≥ 0 for all state s ∈ S, and SP t (s) ds = 1. This constrains the perturbations to states with non-zero transition probability in P t , i.e. the adversary is only allowed to modify the distribution over next states that were already reachable. At the beginning of a trajectory, the adversary is given an initial perturbation budget η 1 , which gets updated after each state transition. On time step t, the adversary is constrained by the remaining budget η t , i.e. they must enforce that δ t (s) ≤ η t for all s ∈ S. To ease notation, we hereafter refer to η = η 1 as the adversary budget. The budget constraint is implemented over entire trajectories, i.e. δ 1 (s 2 ) · ... · δ T −1 (s T ) ≤ η. The adversary therefore needs to maximize the impairment to the agent without wasting their budget.

Environment
Adversary Game dynamics The game between the agent and the adversary goes as follows. On each time step t, the agent observes their state s t and selects an action a t . The adversary then observes their state s t = (P t , η t ) given by the nonperturbed transition kernel P t of the agent and the current budget η t . Using this information, they select an adversarial action (perturbation) such that δ t (s) ≤ η t ∀s ∈ S, generating the perturbed transitionsP t . The agent then transitions into the next state s t+1 ∼P t , a reward r t+1 ∼ R(s t , a t , s t+1 ) is generated, and the remaining budget is updated according to the next state's corresponding perturbation via η t+1 = η t /δ t (s t+1 ). The agent obtains the reward r t+1 , while the adversary obtains the reward −r t+1 . Figure 1 shows an overview of the ACReL game dynamics.
Note that, since the perturbation budget is only affected by the next encountered state s t+1 ∼P t , the budget decreases only if the adversary increased the probability of sampling s t+1 , i.e. if δ t (s t+1 ) > 1. This also implies that if δ t (s t+1 ) < 1, the budget will increase. We emphasize that the adversary may not however deliberately aim to increase their budget. Indeed, since any budget increase is the result of the next state being sampled despite the adversary decreasing its probability, there also has to be an equivalent likelihood that the next sampled state had its probability increased and would result in a budget decrease instead.
Max-min game The general idea of this work is that an adversarial policy ν can be learned to select perturbations that respect the budget constraint, attempting to minimize the rewards collected by following policy π. Combining the agent and adversary naturally leads to the max-min game where E[J η (π, ν)] denotes the expected return collected under policy π perturbed by an adversarial policy ν with initial budget η. Interestingly enough, this formulation implies that the goal of each player is to respectively maximize and minimize the expected return, retrieving the classical risk-neutral RL objective. This means that any standard RL algorithm may be applied almost out-of-the-box to this game. Moreover, the embedded flexibility of the game also allows for the underlying MDP to have continuous action and/or state spaces.

Game Solution
The solution to the game (4) is given by its Minimax Equilibrium.
for which the inequalities hold for any other agent π or adversary ν.
At this equilibrium point, we have the following result. Lemma 1. Suppose π θ and ν ω are expressive enough player parametrizations, meaning that they can represent the optimal players π * and ν * . Then, at the Minimax Equilibrium (π * , ν * ), the agent policy π * is CVaR α optimal for α = 1 η , where η is the adversarial perturbation budget: Proof. Proposition 1 from  established that ] . The result follows by observing that the inf operation will return an adversary in the search space and then taking the max over the policy search space.
The result in Lemma 1 is satisfying in two ways. First, it directly translates the ACReL framework into risk-sensitivity for the agent policy, even though the agent and adversary both have classical risk-neutral objectives. Second, it establishes that the α confidence interval in the CVaR α objective is directly linked to the perturbation budget η. Accordingly, in a real-world scenario where one wishes to optimize for a given α-quantile, setting the initial adversarial budget to η = 1 α will yield the desired risk-sensitive policy at the equilibrium point. Given the parametrized ACReL setting where both the agent and adversarial policies are learned rather than exactly computed, we are particularly concerned with the notion of approximate equilibrium, which is more likely to be encountered in practice.
Interestingly, this approximate equilibrium yields an approximately CVaR-optimal policy. Theorem 1. Suppose π θ and ν ω are expressive enough player parametrizations. Then, at an ε-Minimax Equilibrium point (π , ν ), the agent's policy π is at most ε-suboptimal: Proof. Replacing the two terms on the LHS of Eq. 6 by Lemma 1 and Proposition 1 from  respectively leads to the result.

Gradient-based Algorithm
Following the success of Deep RL to tackle challenging RL problems [Arulkumaran et al., 2017], we aim to leverage advanced (deep) representations for solving ACReL. However, computing the solution of the max-min game (Eq. 4) for players represented by neural networks is not trivial. Indeed, the dependence between the rewards observed by each player makes the optimization objective non-stationary [Fiez et al., 2020], hampering the convergence properties of vanilla gradient-based algorithms. It is therefore necessary to take into account the game structure in the parameter updates of the agent and adversarial policies. Although no gradient-based optimization updates specifically designed for max-min games like ACReL currently exists, such updates do exist for Stackelberg games [Von Stackelberg, 2010]. We therefore cast ACReL under the Stackelberg formulation to derive the desired gradient updates.

Stackelberg Algorithm
A two-player Stackelberg game [Von Stackelberg, 2010] is an asymmetric game played between a leader L and a follower F . Both players aim to maximize their respective payoff functions u L (θ L , θ F ) and u F (θ L , θ F ), given their respective parameters θ L and θ F . The particularity in this game is that θ F always represents a best-response with respect to θ L . Accordingly, the leader can then update its parameters θ L by taking for granted that θ F will be updated to remain optimal with respect to them. This yields the following optimization problem for the leader and for the follower Note here that since θ F are always presumed to be optimal with respect to the leader, they may be seen as an implicit function taking as input the θ L , i.e. θ F = θ F (θ L ). Thus, the optimization problem for the leader only depends on

15:
N = N + 1 16: end while its parameters θ L and the non-stationarity issue arising from the game objective may be circumvented by iteratively optimizing each player parameters independently.
The key to solving a Stackelberg game is to ensure that the follower learns much faster than the leader, so that its parameters always constitute a best response to the leader. We can therefore simply alternate between solving the optimizing problem of each player, resulting in a simple yet effective algorithm. Since max-min games such as ACReL are a special case of Stackelberg games where u L = −u F , we need only to define a leader and follower to apply the Stackelberg algorithm. We select the agent as the leader and the adversary as the follower, but show in our convergence analysis (Section 4.3) that this choice can be reversed.

Practical Implementation
In practice, we adopt common relaxations of the Stackelberg algorithm (Section 4), which have proven effective with GANs [Heusel et al., 2017] and model-based RL [Rajeswaran et al., 2020]. First, we implement near optimal updates of the follower by performing K adv > 1 gradient steps of the adversary (follower) before updating the agent (leader). Second, we use a first-order approximation of the joint gradient to update the leader rather than the computationally expensive exact update. Algorithm 1 shows the resulting ACReL game. Further details on the practical implementation can be found in Appendix A.

Convergence Analysis
Given the following assumption on the MDP, the Stackelberg algorithm (Section 4) converges to the equilibrium of the ACReL game (Eq. 5). Assumption 2. The reward function R and all transition functions P are both smooth and convex.
The smoothness assumption is likely to hold in practice, e.g. many real-world environments like robotics can be considered smooth [Pirotta et al., 2015] and the same can be said about neural networks with ReLU activations [Petersen and Voigtländer, 2018]. Moreover, although the convexity assumption is much more restrictive, convexity is commonly assumed in RL [Pinto et al., 2017, Perolat et al., 2015, Patek, 1997 with minimax objectives and good empirical performance is still observed even when this assumption is not met. Under Assumption 2, we have the following lemma. Lemma 2. The expected return E[J η (π, ν)] is convex with respect to π and concave with respect to ν.
Proof. This follows from the convexity of R and all P.
Building upon Lemma 2, we have the following result.
Theorem 2. The proposed Stackelberg algorithm will converge towards the Minimax Equilibrium of the game.
Proof. This is a well-known result for Stackelberg games in the max-min setting with a convex-concave playoff function (see Fiez et al. [2020]), a condition guaranteed by Lemma 2.
Remember that the Minimax Equilibrium of the game contains a CVaR optimal policy per Theorem 1. Theorem 2 therefore proves that the proposed gradient-based algorithm under the ACReL game formulation constitutes a theoretically justified way to attain a CVaR optimal policy. A last theoretical result follows from the convex-concave objective in ACReL. Corollary 1. For the proposed game, we have Proof. This follows from the convexity Lemma 2, which allows to apply the minimax theorem [Sion, 1958], inverting the min and max terms.
This last corollary is of separate interest, as it notably implies that the Stackelberg algorithm can take any of the players as its leader to achieve the Minimax Equilibrium of the game.

Experiments
We now demonstrate the applicability of ACReL with neural networks on an illustrative toy environment. Specifically, we study the ability of an agent learning under ACReL to recover the true CVaR optimal policy and investigate the adversarial dynamics on the learning procedure. We conduct experiments on a variation of the Gym Minigrid Lava environment [Chevalier-Boisvert et al., 2018]. Figure 2 illustrates this environment where an agent walks in a grid with the aim to reach the green goal tile as fast as possible from the red dot initial location, while avoiding stepping in the orange lava obstacle. An agent state corresponds to the (x, y) coordinates of the agent in the grid. The action space for the agent corresponds to moving into one of the four cardinal directions. At each time step t of a trajectory (episode), the agent incurs a reward penalty of −0.035, motivating the agent to reach the goal using the shortest path. The episode ends when the agent either reaches the goal, generating a reward of +1, falls into the lava, generating a reward of −1, or when the maximum number of 40 steps is reached within the episode, without any additional reward.

Experimental details
Stochasticity The environment is stochastic such that the agent performs random action (instead of the action recommended by the policy π) with probability p. This environment poses an intrinsic risk dilemma to the agent. Indeed, as the agent incurs penalties for every step taken, they want to walk the shortest path, which is close to the lava zone. However, the intrinsic environment stochasticity (p) may push the agent into the lava. This dilemma between minimizing the risks of falling into the lava while also minimizing the number steps for reaching the goal serves as a good minimal illustration of a safety-critical environment. The more importance given by the agent to avoid large negative rewards, the more willing the agent will be to avoid the cliff by walking a longer patch (towards the bottom of the grid). We hereby report the results of experiments with p = 0.1 Further results using p = 0.05 can be found in Appendix C.
ACReL Both the agent and the adversary are trained jointly following Algorithm 1 with K adv = 2, according to a cross-validation over K adv ∈ {2, 4, 8}. Both policies are learned using Actor-Critic PPO [Schulman et al., 2017].
Baselines We employ IQN-CVaR [Dabney et al., 2018] as a first baseline, the CVaR variant of a state-of-the-art risk sensitive distributional RL algorithm. Since our goal is to determine the optimality of the learned policies with respect to the CVaR objective, we also compute the true optimal policies via policy iteration .
To ensure fair comparison, both ACReL and IQN-CVaR are trained under a similar training regime. Namely, all algorithms are executed for a maximum of 5m steps in the environment and agents are all implemented as a singlelayer neural network with 64 hidden neurons. In order to assess the robustness of the approaches, we run each algorithm using n = 10 random seeds. Our codebase is attached as supplementary material for full reproduction of the experiments and figures. Further details on algorithms and training hyperparameters are discussed in Appendix B.

Learned policies
We visualize the agent policies learned after 5m steps by executing each policy in a deterministic environment (p = 0) without any adversary. This allows to observe the decisions made by the agent without the noise induced by environment stochasticity. Figure 3 shows the resulting policies learned with p = 0.1 (see Figure 10 in Appendix C for p = 0.05) using blue shading to indicate the distribution of grid locations visited by the policies, averaged over the random seeds, and red paths indicating the CVaR α optimal policies. As expected, we observe that the optimal policies adopt an increasingly cautious behavior as α decreases, the paths progressively moving further away from the lava. First thing to note is that this tendency is also found both with ACReL and IQN-CVaR. For the CVaR 1 and CVaR 0.01 objectives, both algorithms learn policies that are slightly overcautious. Interestingly, for CVaR 0.04 , ACReL converges more closely to the true optimal policy than IQN-CVaR. This confirms that the performance of ACReL in retrieving CVaR α optimal policies in practice matches the current state-of-the-art in the literature.
However, further investigation reveals that both ACReL and IQN-CVaR suffer from convergence instabilities. More specifically, for both algorithms, some runs result into sub-optimal policies even after 5m time steps. We believe that those issues arise from the inherent difficulty of the task, which strongly depends on exploration due to the simplistic agent state representation. Indeed, since the agent only observes its current position, the goal can only be reached "by chance" the first time. Therefore, one unlucky agent may seldom observe the goal state reward and learn a policy that does not aim for the goal state, but rather simply tries to avoid getting pushed in the lava. Despite these challenges, both strategies converge in the vast majority of runs (see Appendix C).

Adversarial dynamics
Having established that ACReL is competitive when it comes to retrieving CVaR α optimal policies, we now study the adversarial policy and its impact on the agent policy. To achieve this we first visualize the ACReL agent policies learned after 5m steps by executing them in the stochastic environment to collect 300k trajectories, with and without the adversary. Figure 4 shows the resulting policies (learned with p = 0.1) using blue shading to indicate the number of times each grid position was visited over all trajectories, averaged over the random seeds. Numbers indicate the probability that the agent may perform an action different from the action recommended by the policy π. In order to display accurate estimates, only the probabilities for the locations that the agent visited at least 1500 times are displayed. Probabilities greater than 0.1 (environment stochasticity p) indicates that the adversary is spending some of its budget to alter the agent policy in this location.
With adversary As expected, we first observe that the agent is pulled closer to the lava zone in the presence of an adversary (top row). Note that the adversary is mostly active at the beginning of a game episode, regardless of the amount of perturbation budget. The beginning of the game is indeed the riskiest situation for the agent since the starting point is very close to the lava (top-left corner). More sophisticated adversarial strategies emerge when the adversary benefits from a higher budget. When the agent is far from both the lava and the goal, the perturbation probability drops below 0.1 (the natural environment stochasticity), meaning that the adversary tends to give more leverage to the agent in this zone. This allows the adversary to recover some budget and become more powerful when the agent gets closer to the goal, hence closer to the lava. This is also confirmed by looking closely at the adversarial policy over single trajectories (Appendix C.1).

Related Work
Adversarial RL Although typically used in supervised learning, adversarial learning [Kurakin et al., 2017] has been applied in RL under the robust MDP formulation. In robust MDP the agent aims to optimize the worst-case return of a policy under some uncertainty limitations, implemented as bounded adversarial perturbations. These perturbations can occur over state representations [Pinto et al., 2017, Kamalaruban et al., 2020, the policy [Mandlekar et al., 2017, Tessler et al., 2019, Li et al., 2019, or the reward function [Lin et al., 2020]. However, since the robust MDP framework defines its perturbation limitation over every single time step, setting the actual limitation value is a challenging task. Because the adversary may reach its perturbation limit at every step, a large limit may produce overly conservative policies while a small limit may hamper the actual robustness of the learned policy [Mozian et al., 2020]. In contrast, our proposed adversary budget is defined over a whole trajectory, ensuring that the worst possible adversarial perturbation cannot occur at every step, an arguably more plausible scenario.
CVaR RL Optimization of the CVaR criterion in RL have been extensively studied in the tabular and linear settings. The proposed algorithms range from policy gradient  and Q-learning , to actor-critic methods [Tamar and Mannor, 2013]. While these approaches are all limited to either tabular or lowdimensional action and state space settings, the gradient-based algorithm considered in this work is compatible with neural network settings. Interestingly,  proved a link between a policy's robustness to modelling errors of varying strength and CVaR optimality. Although our adversarial model is inspired by this result, our proposed game is distinguished by the key fact that our adversary is a learnable player.
More recently, distributional RL [Bellemare et al., 2017, Dabney et al., 2018 has been used to learn CVaR optimal policies in high-dimensional settings [Keramati et al., 2020, Zhang and. This approach has seen growing usage, largely due to its empirical efficiency and its ability to incorporate a wide variety of risk measures in its objective, not exclusively the CVaR. However, since distributional RL does not generally converge over the whole return distribution [Bellemare et al., 2017], any risk measure optimization on the learned distribution is not theoretically guaranteed to converge to the true optimally risk-averse policy [Dabney et al., 2018]. In this work, we provide a theoretical guarantees on the optimality of the policy obtained from the proposed strategy.
The closest work to ours would be Robust Adversarial Reinforcement Learning (RARL) [Pinto et al., 2017], where a policy is learned by allowing an adversary to apply external forces to the environment according to a CVaR objective. The action space of the adversary is therefore different from the one in ACReL, as it applies various problem-specific perturbations to the model. This adversarial formulation notably implies that their CVaR objective is only an informal one, as one cannot link the perturbation range given to the adversary to a specific CVaR α objective. In contrast, we establish a clear, theoretically justified, connection between the budget of the adversary and the α-quantile optimized by the agent.

Conclusion
In this work, we introduced ACReL, an adversarial game designed to compute risk-sensitive policies with respect to the Conditional Value-at-Risk (CVaR) risk. This adversarial game limits an adversary's perturbations to be within a specified budget over entire trajectories and to only change next state transitions for an agent. We proved that the the resulting policy at the game's equilibrium is CVaR optimal, with the result also holding around the neighborhood of the equilibrium. We then showed a gradient-based algorithm using the Stackelberg formulation of the game to solve the game, both proving its convergence under sufficient conditions and presenting key considerations for a practical implementation. We put our method to the test on an artificial risky environment, illustrating that ACReL matches the performance of a state-of-the-art baseline in successfully retrieving CVaR optimal policies.
Given the fact that this is the first game-theoretic perspective on CVaR RL, we expect this paper to be a building block towards connecting risk-sensitivity in RL with the field of Game Theory. Notably, we believe it may be possible to link our adversarial framework with other risk-sensitivity measures by allowing the budget to vary during training instead of keeping it fixed.
One possibly interesting application of our method is with regards to the Sim2Real domain, where one wishes to optimize to train an RL agent on a high-quality simulation environment before real-life deployment. Since this domain is naturally concerned with risk-sensitivity and supposes access to a simulator to access and perturbate the true next state transitions, it appears highly likely that our proposed approach can be of use in this context. In future work, we would like to apply ACReL to the Sim2Real application to study the scalability of ACReL, both with respect to task difficulty and neural networks complexity.

A Practical Algorithm Details
Practical Stackelberg Algorithm Recall the Stackelberg optimization problems for the leader and for the follower θ F ∈ arg max θ u F (θ L , θ).
As is usually done in gradient-based methods, we may solve the leader's optimization problem using gradient ascent. Making sure that the follower remains optimal in between leader updates, we use the following bi-level procedure: where β is a learning rate hyperparameter, ∂ ∂θ is a partial derivative gradient and updates are done sequentially for each parameters. Note that since the leader update 8 is done using θ k+1 F , optimal with respect to θ k L by definition, alternating between these two updates does indeed respect the Stackelberg game requirements. Applying the above bi-level procedure remains challenging in practice however. First, the arg max operation in 7 is actually an optimization problem on its own which may require an impractical amount of time to compute. Based on the intuition that best responses for consecutive leader parameters should be near each other for a small enough β, we approximate the arg max by doing a few gradient ascent steps. Second, while the leader's partial gradient ∂ ∂θ u L (θ, θ k+1 F ) may be computed exactly to incorporate the implicit relation between the leader and follower, this exact update requires the computation of a Jacobian matrix which is computationally intensive. Instead, we simply use a a first-order estimate, using the total gradient ∇ θ u L (θ, θ k+1 F ), which is biased may be computed more efficiently.
Perturbation rescaling and budget constraint At every time step t, the adversary produces perturbations δ t = ν(P t , η t ). Recall that, in order to be admissible, the adversary's output δ t has to produce perturbed transitionsP t = P • δ t that are a valid distribution and every δ i has to be less than the remaining budget η t .
In order to respect both constraints simultaneously, we propose a two-step normalization procedure to ensure the final output is an admissible perturbation. We begin by normalizing the adversary's raw output y to yield a perturbation δ that makesP = P • δ a distribution 1 δ i = y i / j P j y j .
If the δ generated by the normalization respects the budget constraint, then we can return δ directly. However, if the perturbation δ is over budget, we have to reduce it to a versionδ within budget. Exploiting the convexity of probability spaces, we apply the following transformation: where δ := max i δ i . The transformation 9 benefits from the following properties: 1. it does not move the unperturbed transitions (δ i = 1 ⇐⇒ δ i = 1); 2. it is strictly increasing (i.e.δ i >δ j ⇐⇒ δ i > δ j ); 3. it will bring each δ i closer to 1 (i.e. |δ i − 1| > |δ i − 1|).
The obtained properties ensure that the overall intuition behind the adversary's proposed perturbation is kept when applying the correction.

B Experimental details
Toy Risky Environment Figure 5 is a visual representation of the Lavagrid environment used to conduct our experiments. The agent's starting position, referred to as S in the main paper, is shown here as a red dot. The goal tile where the agent receives a large reward, referred to as G in the main paper, is shown here as a green square. Wavy orange tiles represent "lava" squares, which the agent intuitively learns to keep away from because they produce a large negative reward. In our experiments, the agent takes as input their current coordinates (x, y) in the grid which is a vector of length 2 and returns an action as a one-hot-vector of size 4. For ACReL, the adversary takes as input a concatenation of s t , the value of their remaining perturbation budget η t , and the probabilities p t that each of the 4 possible actions will be the one executed, making the adversary input a vector of 7 elements. The adversary returns perturbed probabilitiesp t over possible action executions. This particular choice of representation for the agent's state and action spaces were made after initial experiments proved unsuccessful when using the complete next state distributions P t . We estimate that sparse transitions like the ones encountered in our selected gridworld make the adversary task more difficult. This is why we proposed the state and action spaces described above for the adversary, which have the benefit of being drastically smaller while preserving all the necessary state information and action range.
In order to evaluate the robustness of both methods, we replicate each instance of the game 10 times, each time with a different random seed. The environment is stochastic with probability (p = 0.1) for the agent to perform a random action instead of the chosen action a t . For ACReL, the environment's seed (governing its randomness), the agent (governing the initialization of its policy and the action selection process), and for adversary's (governing the initialization of its policy and the perturbation prediction process) are reinitialized. For IQN-CVaR, the environment's seed (governing its randomness), as well as the agent's (governing the initialization of its policy) are reinitialized.
ACReL Both the agent and the adversary are trained using PPO [Schulman et al., 2017] with shared hyperparameters. For both players, the actor and critic are Multi-Layer Perceptrons (MLP) with 1 hidden layer of 64 nodes and tanh as activation function. A clipping value of 0.2 is used. The Generalized Advantage Estimator hyperparameter λ is set to 0.95. The entropy term coefficient is set to 0.1 and the value loss term coefficient to 0.5. The maximum norm of the gradient is set to 0.5. Both players use an Adam optimizer with their own decaying learning rate that decreases linearly from 0.005 to 0.0001 over the course of training. The ε for Adam is set to 1e − 8.
During training, an update of the parameters occurs every 10k time steps. The adversary is updated K adv = 2 times in between each agent's update (see in Algorithm 1). For the update, the batch size is set to 256 observations and there are 4 gradient steps done.

IQN-CVaR
We use a publicly available library, Tianshou , for the implementation of IQN, We simply make the modifications on the provided implementation to match the IQN-CVaR algorithm as described in the original paper [Dabney et al., 2018]. The network architecture is the same as in ACReL also using an Adam optimizer. The training procedure is separated in two portions. In the first portion, lasting for the first 2.5M steps, the ε value in the ε-greedy action selection linearly decreases from 1.0 to 0.1 while the learning rate is set at 0.002. In the second portion, lasting for the last 2.5M steps, ε is kept fixed at 0.1 and the learning rate is lowered at 0.0002.
Updates are done every 10 time steps by sampling a batch of B = 128 transitions from a replay buffer with a maximal capacity of 500 000 transitions. For all other hyperparameters not named (e.g. the number of τ quantile samples), we keep Tianshou's default values.
Compute requirements All experiments are run on a single computer equipped with a Nvidia P100 GPU, using 4 CPU cores and less than 5GB of RAM. Each training run takes about 3h for ACReL and 1h for IQN-CVaR. It is to be expected that ACReL takes slightly more time to train, for the simple reason that each time step in the environment requires calling two neural networks (the agent and adversary) instead of a single one with IQN. The policy visualization experiments ran using 300k trajectories for ACReL take around 3h to complete as well.
C Additional Results (c) No budget left Figure 6: Example interactions between the adversary and agent in ACReL. Colored arrows illustrate the amplitude of perturbation applied to the initial probabilities.
For a finer-grain analysis of the adversarial dynamics, we detail in Figure 6 interesting interactions between the agent and adversary over a single trajectory. We notice three distinct interaction patterns. The first pattern corresponds to the situation where the adversary spends all their budget at the beginning of the episode and successfully wins the game by pushing the agent into the lava. The opposite interaction occurs when the adversary spends all their budget at the beginning of the episode but fails to make the agent hit lava. In this case, since the adversary cannot influence the agent anymore, the trajectory continues as the agent pleases, with the usual intrinsic environment stochasticity. A third and perhaps most interesting interaction occurs when the adversary spends a large amount of budget at the beginning but keeps enough budget to remains able to act during the rest of the episode. Interestingly, the adversary increases the winning direction probability (right) which apparently helps the agent reaching their goal. In the end of the episode, when the agent has to move closer to the lava before reaching the goal state, the adversary plays a final move, spending all its budget towards moving the agent directly next to the lava.

C.2 In-Depth Run Analysis
While we reported learned policies averaged over n = 10 random seeds in the main paper, we now present each separate training run's results. The agent policies obtained with ACReL are displayed in Figure 7 while those for IQN-CVaR are in Figure 8. In Figure 9, we also report IQN-CVaR's results when trained for 10M steps, to view whether or not IQN-CVaR's convergence instabilities may be solved by simply increasing the training duration.
Three different training results can be observed on the individual training run's learned policies. A first pattern, is the U-shaped trajectories that is obtained when the policy successfully reached the goal state by going around the lava obstacle. This first and most common pattern contains the trajectories which observe the most rewards, as any trajectory that reaches the goal state is guaranteed to obtain a sum of total rewards R = T t r t ≥ −0.4, corresponding to the cost of 40 steps (-1.4) and the goal reward of +1. A second pattern is the one where the agent simply wastes its time reaching a fixed wall tile and then staying in it for the remainder of the episode. This pattern is guaranteed to produce a sum of rewards R = −1.4, corresponding to paying the step cost −0.035 for the maximum number of allowed steps 40. A third noticeable pattern is the one where the agent learns to immediately throw themselves in the lava obstacle. This pattern is guaranteed to obtain a sum of rewards R = −1.07, corresponding to the cost of the two steps required to reach the lava and the lava reward of -1.
Intuitively, depending on whether or not the agent's exploration reached the goal state a sufficient number of times during training, one should expect learned policies to either harbor the first or third pattern, as the second one is the least rewarding. We accordingly refer to the second pattern as a convergence failure. Table 1 displays the number of convergence failures over the 10 considered seeds.    We first note that ACReL is less prone to convergence failure than IQN-CVaR under a similar training regime of 5M steps. Although increasing the number of steps to 10M for IQN-CVaR does seem to alleviate the convergence failure rate, it still does not manage to outperform ACReL with twice the training steps. We hypothesize that this may be a symptom of IQN-CVaR's lack of theoretical convergence guarantee for risk-sensitive objectives or simply a result of the environment's intrinsic exploration difficulty. Further experiments would be needed to explain this performance difference and we leave them as future work.

C.3 Harder environment setting
In this section, we provide additional results on the evaluation of our method on a different configuration of the environment. In the main paper, the environment is stochastic with probability (p = 0.1) for the agent to perform a random action instead of the chosen action a t . Here, we consider a different configuration where the probability of random action is set to p = 0.05. The considered budgets for the adversary remain the same (η ∈ {1, 25, 100} respectively corresponding to learning a CVaR α of α ∈ {1, 0.04, 0.01}). This task is harder for the adversary because it has the same budget but must perform bigger perturbations to influence the agent's trajectories since the stochasticity of the environment is two times lower.
Red trajectories in Figure10 correspond to the resolution of the environment with CVaR Policy Iteration. As expected, Figure 10a shows that in the absence of risk-sensitivity (α = 1), the optimal behavior is to follow the cliff by taking the shortest path to the goal. However, in the presence of risk-sensitivity (α < 1), Figures 10c and 10e show that the the optimal behavior is a careful path that deviates from the lava. However, we notice that the optimal behavior corresponding to a CVaR 0.01 and CVaR 0.04 are the same. This is because the stochasticity of the environment is low (p = 0.05), therefore the risk of accidentally falling into the lava is lower.
Blue trajectories in Figure 10 display the learned agent policy averaged over the 10 seeds for each of the 3 considered CVaR α optimization tasks. The Figure confirms that our adversarial learning method results in a safer policy as well. Furthermore, the averaged behavior is consistent over 10 different randomness realizations. The noticeable noise in the averaged agent policy displayed in Figure 10 is due to punctual convergence instabilities. Despite the instabilities inherent to the training procedure, the agent trained with ACReL consistently displayed convergence for the 3 considered tasks. IQN-CVaR converges successfully for CVaR 1 and CVaR 0.04 but fails to resolve the environment for CVaR 0.01