Most Reinforcement Learning (RL) approaches usually aim to find a policy that maximizes its expected return. However, this objective may be inappropriate in many safety-critical domains such as healthcare or autonomous driving, where it is often preferable to optimize for a risk-sensitive measure of the policy's return as the learning objective, such as the Conditional-Value-at-Risk (CVaR). Although previous literature exists to address the problem of learning CVaR-optimal policies in Markov decision problems, it mostly relies on the distributional RL perspective. In this paper, we solve this problem by rather proposing an approach based on a game theoretic perspective, which can be applied on top of any existing RL algorithm. At the core of our approach is a twoplayer zero-sum game between a policy player and an adversary that perturbs the policy player's state transitions given a finite budget. We show 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. We illustrate the applicability of our approach on a risky artificial environment, presenting the different policies learned for various adversary budgets.
Reinforcement Learning (RL)
This has motivated the community to design risk-sensitive
algorithms, where the agent is trained to account for the
possibility of catastrophic events. One way to proceed is to
include a risk measure
In this work, we rather tackle the CVaR RL problem
in a game-theoretic setting. Looking at a problem from a
game-theoretic perspective has helped advance other fields
like Generative Adversarial Networks (GANs)
The rest of the paper is separated as follows. Section 2 first introduces the necessary background and notation. Following is an overview of the related work in Section 3. Next, we present in Section 4 an overview of our proposed game formulation alongside its relevant properties, which include the convergence to a CVaR RL policy at equilibrium point. In Section 5, we develop a gradient-based algorithm based on the Stackelberg game formulation to solve the presented game, presenting both a theoretical analysis of its convergence as well as key practical concerns. Lastly, we illustrate the validity of the method in an artificial gridworld experiment (Section 6).
2
In RL, an agent interacts with an environment, trying to identify actions that lead to the highest rewards. The most common RL formulation for the environment is that of a Markov Decision Process (MDP) framework. An MDP M is represented by a tuple hS; A; P; R; ; i, where S is the state space, A is the action space, P : S A ! [0; 1]S is the transition probability function which governs the evolution of the system, R : S A ! R is the reward function, 2 [0; 1) is a discount factor and is the initial state distribution. We formalize an agent’s decisions as following a policy : S ! [0; 1]A that generates distributions over which actions to take for each state from parameters 1.
A policy’s actions not only generate immediate rewards but also influence future rewards because they rule the next state the agent will end up in. This is why the performance of a policy is measured by balancing immediate and distant rewards, using a measure called the random return: 1 J ( ) := X trt; t=0 (1) where is a discount factor, at (st), st+1 P(st; at) and rt R(st; at). Due to the stochasticity that may be present in either the reward function, the policy’s action selection or the environment transitions, the random return J ( ) is accurately defined as a random variable. The usual objective in RL is to find the policy that maximizes its expected return, which boils down to finding = arg max E[J ( )].
Let Z be a random variable with a bounded expectation E[Z] < 1 and cumulative distribution function F (z) := P(Z z). In this paper, we interpret Z as a return to be maximized. The Value-at-Risk (VaR) at confidence level 2 (0; 1] represents the worst 1 quantile of Z, i.e., VaR (Z) := minfzjF (z) g. Analogously, the 1For ease of notation, we will only write we are talking about a parametrized policy parametrized function throughout the paper. when it is clear that . This applies for any
dence level is defined as
CVaR (Z) := min w2R
1 w +
E [max(Z w; 0)] : (2) If Z has a continuous distribution, the CVaR measure can be written as
CVaR (Z) := E [z j z
VaR(Z)] : (3) Intuitively, the CVaR (Z) measure can therefore be viewed as the mean over the -quantile worst values of Z. Since Z represents 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 safetycritical domains.
To measure the level of risk associated with a policy , the CVaR measure defined in (3) can be applied to the random discounted return J ( ) defined in (1). Optimizing for this yields the CVaR RL objective = arg max CVaR (J ( )) : (4) This objective, which differs from the traditional expectation maximization goal, can be viewed as finding a risk-sensitive policy. Indeed, by having the optimal CVaR return, the optimal policy is maximizing the expectation over its worst -percentile trajectories. Since the expectation is now taken over a small, disadvantageous subset of all returns rather than over all of them, the optimal policy is more sensible towards avoiding the probability of large negative returns. In practice, this means that optimizing for the CVaR RL objective (4) will produce policies that accept to reduce their expected performance, so long as it means they avoid catastrophic trajectories in return.
Let us take a moment to note here that it is well known
that the optimal policy for the CVaR RL objective can
be history-dependent
3
Although typically used in the supervised learning setup,
adversarial learning
More similar to the current work, Mandlekar et al. (2017) use an adversary to perturb the action selection policy of a RL protagonist at every time step. However, their adversary consists in gradient-based perturbations which do not adapt to the policy of the protagonist. In the formulation tackled in the current work, the antagonist strategy is jointly learned with the protagonist strategy, resulting in an antagonist strategy adapted to battle the protagonist.
Broadly speaking, risk-sensitivity in RL represents the ensemble of methods that aim at reducing the level of risk associated with the learned policy. Different risk measures have been proposed in the literature to address this problem.
First, numerous approaches have been proposed to
explicitly balance the expectation and variance of the return of a
policy
One other popular alternative to incorporate
risksensitivity is the use of exponential utility functions
Many algorithms have been proposed to find optimal
policies with respect to the CVaR criterion. Proposed
algorithms range from policy gradient
More recently, distributional RL
The closest work to ours would be Robust Adversarial
Reinforcement Learning (RARL)
Before diving into the explanation of our proposed adversarial game, let us first present the two assumptions necessary on the target MDP for the game to be applicable. Assumption 1. The MDP has stochastic state transitions P.
The stochasticity is required because it is precisely upon those state transitions that the antagonist will be acting. This assumption is the least restrictive, as a large number of MDPs are already stochastic in nature. Furthermore, any deterministic transition function P could be made stochastic by adding a noise component, either via "-random sampling for discrete states or adding a Gaussian noise " N (0; ) for continuous states.
Assumption 2. It is possible to access the state transitions P and arbitrarily modify their non-zero values.
This assumption is the one that allows the antagonist’s actions to be registered. This is a much more restrictive assumption and is only likely to be met in artificial environments over which the user has a lot of control. Notably, given an MDP with added noise as described above, it should be relatively straightforward to meet this assumption by accessing the analytical formulation of the added noise component.
We aim to learn a risk-sensitive policy with respect to the
CVaR risk measure. To do so, we leverage
To explain our game setting, let us first define time step transition dynamics Pt = P( j st; at) 2 [0; 1]jSj from a given trajectory = f(st; at; rt)gtT=1, where T is the trajectory’s duration. At time step t, the antagonist is given direct access to Pt and allowed to perturb it with a multiplicative probability perturbation t 2 (0; 1)jSj, yielding perturbed transitions P^t = Pt t, for the Hadamard (pointwise) product. A perturbation is admissible if it generates a valid probability distribution P^. Let t be the set of all perturbations t admissible for a given Pt and = 1 ::: ::: T be the set of all possible perturbations of a trajectory . We can define a trajectory perturbation budget 1 and constrain to contain only perturbations within an budget st rt st+1 rt+1
at Protagonist Environment
Antagonist −rt+1 δt ηt Pt ; (5) by posing the admissible perturbation envelope
= = f tgtT=1 j 1(s1) ::: T (sT ) where t(si) represents the antagonist’s perturbation towards next state si at time step t. Note here that, since perturbations are multiplicative in nature, = 1 represents an empty budget, meaning that the antagonist could not apply any modifications to next state transitions.
This definition and limitation of the antagonist’s actions enjoy two principal interesting properties. First, since the antagonist is only given a limited budget for each trajectory, they have to be efficient with their perturbations, trying to maximize the damage to the protagonist’s return without wasting their budget. Intuitively, the role of the budget can be seen as a way to ensure that the antagonist cannot force the worst possible scenario to occur at every time step. Secondly, the fact that the antagonist perturbations are done via a Hadamard product constrains the perturbations to states with non-zero transition probability by default. Essentially, this means that the antagonist is only allowed to modify the distribution over next states that were already reachable.
The main idea of this paper is that an antagonist can be learned to select perturbations within the admissible perturbation envelope defined in (5), attempting to minimize the protagonist ’s reward. Combining the protagonist and antagonist naturally produces the two-player zero-sum game (6) max min E [J ( ; )] ; where E[J ( ; )] represents the expected return collected from a protagonist with admissible perturbations sampled from an antagonist respecting a budget . Interestingly enough, this formulation implies that both players’ goals are to respectively minimize and maximize the expected return, retrieving the classical RL objective. This notably means that any classical RL algorithm like actor-critic methods or Deep Q-Network may be used without fundamental changes for our game. Moreover, the embedded flexibility of the game also allows for the underlying MDP to have continuous action and/or state spaces.
We note that both the protagonist and antagonist players are well defined under the MDP framework for a shared environment. On one hand, the protagonist player’s MDP remains exactly the same, with the only modification that next states are sampled from P^t rather than Pt. On the other hand, the antagonist receives as input states s0t = (Pt; t) 2 S0 = [0; 1]jSj [1; 1) and outputs perturbed transitions P^t = Pt t subject to P^t being a distribution over next states and t(s) t for all states. Next antagonist states s0t+1 are selected by first sampling the next protagonist state st+1 from P^t, then sampling the next protagonist action at+1 from (st+1), and finally observing the next transition distribution Pt+1. Lastly, since the game is zero-sum, the antagonist’s reward is simply rt+1. An overview of the interaction between the protagonist, antagonist and environment is shown in Figure 1.
The solution concept to the game (6) is given by its Minimax Equilibrium.
At this equilibrium point, we have the following interesting result.
Lemma 1. Suppose and ! are expressive enough player parametrizations, meaning that they can represent the optimal players and . Then, at a Minimax Equilibrium point ( ; ), the protagonist’s policy is CVaR optimal for = 1 , where is the antagonist ’s perturbation budget:
max min E [J ( ; )] = max CVaR 1 [J ( )] :
Proof. Proposition 1 from
0 If the parametrization of the antagonist is expressive enough, the inf operation will return an antagonist in the search space, implying that one can look for the best available antagonist for a protagonist to find the CVaR of its returns. The result follows by taking the max over all possible protagonists, where we once again use the fact that is expressive enough to guarantee the existence in the parameter search space.
The result in Lemma 1 is satisfying in two ways. First, it directly connects our adversarial framework to risksensitivity for the learned protagonist policy, even though the protagonist and antagonist’s objectives remain axed on expectation maximization. Secondly, the equation establishes that the confidence interval in the CVaR objective is directly linked to the budget perturbation via = 1 .
Given our parametrized setting where players are learned rather than exactly computed, we are actually more interested in the notion of approximate equilibrium, which is more likely to be encountered in practice.
Definition 2. ("-Minimax Equilibrium). Let V := E [J ( ; )], the value at the Minimax Equilibrium ( ; ). An "-Minimax equilibrium is a pair of players ( 0; 0) where
V
min E [J ( 0; )] and max E [J ( ; 0)]
V " " (8)
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 ( 0; 0), the protagonist’s policy 0 is at most "-suboptimal: max CVaR 1 [J ( )]
CVaR 1 [J ( 0)] " Proof. Taking the first inequality in (8), we have () ()
V V min E [J ( 0; )] CVaR 1 [J ( 0)] "
" max CVaR 1 [J ( )]
CVaR 1 [J ( 0)]
";
first leveraging Proposition 1 from
5
Having established the favorable properties of an approximate equilibrium of our proposed game, we only need to find an algorithm that can reliably reach it. First note that, in order for the algorithm to be able to tackle challenging problems, we wish both players to be used with highcapacity function approximators such as neural networks. Therefore, the algorithm we are looking for should not only converge towards the Minimax Equilibrium, but also do so using gradient-based updates.
However, computing the solution to the minmax game
in (6) for players represented by neural networks is not a
simple task. Indeed, the dependence of each player’s
reward on the other makes the optimization objective
nonstationary
An essential step to achieve stable learning of the game is to take into account the game’s structure in the parameter updates. Although there aren’t good gradient-based optimization updates specifically designed for minimax games like ours, such updates do exist for Stackelberg games. We therefore cast our game under the Stackelberg formulation, allowing us to derive our desired gradient updates.
A two-player Stackelberg game is an asymmetric game played with a leader l and a follower f . Both players aim to maximize their respective payoff functions ul( l; f ) and uf ( l; f ), where represents the parameters of a given player. The particularity in this game is that the follower’s parameters always represent a best-response with respect to the leader’s parameters. Accordingly, the leader can then pick its parameters by taking for granted that the follower’s parameters will be optimal with respect to them. This yields the following optimization problem for the leader l 2 arg max and for the follower ( ul( ; f0 ) ) 0 f 2 arg max uf ( l; f ) ;
f f 2 arg max uf ( l; ):
The key intuition to note here is that, since the follower always has optimal parameters with respect to the leader, then the follower parameters may be seen as an implicit function taking as input the leader’s parameters f ( l). In turn, this allows the leader to exploit this optimal-response form of its follower to update its own parameters towards its own goal.
Intuitively, updating both player’s parameters may be viewed as a bi-level optimization procedure. In order to solve a Stackelberg game, we can therefore simply alternate between solving each player player’s respective optimization problem, producing a simple yet effective algorithm.
As Stackelberg games are a generalization of minimax games such as ours, this Stackelberg algorithm only requires us to establish a leader and a follower to be able to find our game’s equilibrium. We arbitrarily select the protagonist as the leader and the antagonist as their follower, but show in the following convergence analysis that this choice can be reversed without problem.
Given some assumptions on the environment MDP, the Stackelberg algorithm described previously converges to the equilibrium of our game.
Assumption 3. The reward function R and all transition functions P are both smooth and convex.
Assumption 3 is quite restrictive in practice. Indeed, while
the smoothness portion of it is likely to hold in practice, e.g.
many real-world environments like robotics can be
considered smooth
When Assumption 3 is met, 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 theorem. 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 two-player zero-sum setting with a convex-concave playoff function (see Fiez, Chasnov, and Ratliff (2020)), a condition guaranteed by Lemma 2.
Remember that the (approximate) Minimax Equilibrium of the game contains a CVaR (approximately) optimal policy. It follows that Theorem 2 constitutes the proof that our overall framework (the game and the proposed algorithm), is indeed a theoretically justified way to attain a CVaR optimal policy. A last theoretical result follows from the game’s convex-concave objective.
Corollary 1. For the proposed game, we have
min max E [J ( ; )] = max min E [J ( ; )] :
Proof. This follows from the convexity of the payoff
function E [J ( ; )] (Lemma 2), which allows us to apply the
minimax theorem
This last corollary is of separate interest, as it notably implies that the Stackelberg algorithm can take any of the players as its leader.
In practice, we adopt a few relaxations of the exact
Stackelberg algorithm described above. The adopted relaxations
have proven effective in domains like GANs
Another important consideration is the fact that the protagonist needs to output perturbations within the admissible perturbation envelope for every collected trajectory. To do so, we propose to simply keep track of the remaining antagonist budget after every time step t, updating it according to the realized perturbation (consumed budget) t(st+1). A convex transformation and a rescaling function are applied to the budget predictions in order to constrain the predictions to give a probability distribution when multiplied with the state probability. A pseudocode of the overall algorithm incorporating all the above relaxations can be seen in Algorithm 1.
6
We conduct experiments on a variation of the Gym
Minigrid Lava environment
P^t; rt+1 t(st+1) 8: 9: 10: 11: end while 12: Update 13: Nupdates = Nupdates + 1 14: end while R(st+1)
. Update remaining budget or ! according to Nupdates and Kant.
Algorithm 1: CVaR Adversarial Stackelberg Algorithm Require: (protagonist), ! (antagonist), (perturbation budget), Kant (number of intermediate antagonist steps) 1: Nupdates = 0 2: while training not done do 3: Get initial state st 4: = . Remaining antagonist budget 5: while st not terminal do 6: at (st); Pt = P(st; at) 7: t = !(Pt; ) grid). A lava zone lies between the starting point and the goal (wavy orange squares). A state in this game corresponds to the (x; y) coordinates of the protagonist and the state space S corresponds to the set of all possible coordinates in the grid. The action space A for the protagonist corresponds to moving into one of the four cardinal directions (up, down, right, left). The environment is stochastic with probability (p = 0:05) for the protagonist to perform a random action instead of the chosen action at. At each time step t of a game episode, the protagonist incurs a reward penalty of 0:035, motivating the protagonist to reach the goal using the shortest path. The episode ends when the protagonist either (i) reaches the goal, resulting into a reward of +1, (ii) falls into the lava, resulting into a reward of 1, or (iii) when the maximum number of 40 steps is reached within the episode.
As the protagonist aims to reach the goal location, the antagonist rather aims to push the protagonist into the lava zone. Since the antagonist acts upon a limited budget, the protagonist is able to reduce the chances of falling into the lava by just moving farther away from the lava. As the protagonist also incurs penalties for every step taken, they nonetheless want to avoid making unnecessary steps, eventually needing to be close to the lava zone. This dilemma between minimizing the chances of falling into the lava while also making sure that no unnecessary steps are taken serves as a good minimal illustration of a safety-critical environment. Indeed, the more weight the protagonist will put on avoiding large negative rewards, the more it will be willing to take the time to get to the lower cases of the grid before crossing from left to right. than 0:05 indicates that the antagonist is disturbing the transition probabilities at this location since the probability differs from the natural environment randomness.
Both players are trained using Actor-Critic PPO
algorithms
Both algorithms use an Adam optimizer with their own decaying learning rate that decreases linearly from 0:005 to 0:0001 each time their parameters are updated. Further details on the hyper-parameters and implementation are discussed in our publicly available implementation. Our codebase is made publicly available2 for full reproduction of the experiments and figures.
We consider three instances of the described game: the case where there is no antagonist, which corresponds to having an antagonist with a perturbation budget = 1 (as a reference for comparison), as well as having an antagonist with two different budgets, 2 f25; 100g. Without an antagonist, the game corresponds to the classical problem of maximizing the excepted returns. When the antagonist has a positive perturbation budget, this corresponds to optimizing a CVaRoptimal policy, i.e. CVaR0:04 for = 25 and CVaR0:01 for = 100. In order to evaluate the robustness of the proposed approach, we replicate each instance of the game 10 times, each time with a different random seed for the environment (governing its randomness), for the protagonist (governing the initialization of its policy and the action selection process), and for the antagonist (governing the initialization of its policy and the perturbation prediction process).
In order to visualize the protagonist strategy in any game instance, we execute the policy learned by the protagonist agent in a deterministic environment (p = 0) without the antagonist. This allows to observe the decisions made by the protagonist agent without perturbations. To visualize the antagonist strategy in a given game instance, we execute the policy learned by a protagonist under this instance, i.e. the stochastic environment (p = 0:05) in presence of the antagonist. For each state in the grid, we estimate the probability that the protagonist performs a different action than their preferred action in that state. A probability estimate equal to 0:05 indicates that the antagonist does not hamper the protagonist on this location since this corresponds to the environment randomness (p). A probability greater or lesser 2https://github.com/TortillasAlfred/CvarAdversarialRL
Figure 3 displays the learned protagonist policy averaged over the 10 seeds for each of the considered game instances. As expected, Figure 3a shows that the protagonist learns the shortest path to the goal in the absence of an antagonist ( = 1). However, when there is an antagonist ( > 1), Figures 3b and 3c show that the protagonist learns a careful path that deviates from the lava. More specifically, the stronger the antagonist (the larger the perturbation budget ), the more careful the protagonist has to be in order to avoid getting pushed into lava. This confirms that the presence of an antagonist agent when learning the protagonist policy results in a safer policy.
Note: The noticeable noise in the averaged protagonist
policy displayed in Figure 3b is due to convergence
instabilities, which caused the protagonist to fail reaching the goal
in 2 out of the 10 tested seeds. This may be due to the
protagonist being particularly unlucky in these realizations of
the environment and/or in the initialization of their policy.
In other applications of game theory with gradient-based
algorithms (e.g. Generative Adversarial Networks
Figure 4 shows 300k trajectories obtained by executing a protagonist (single seed) in a stochastic environment (p = 0:05) in presence of the antagonist used during their training. The number on a given square indicates the probability that the protagonist will perform a different action than at when st corresponds to that location. This includes both the natural environment randomness as well as the influence of the antagonist. Figures 4b and 4c show that the antagonist 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 protagonist since the starting point is very close to the lava (top-left corner). More sophisticated adversarial strategies emerge when the antagonist benefits from a higher budget (see Figure 4c). For instance, when the protagonist gets far from the lava, we see that the antagonist exploits the borders of the grid to force the protagonist into accumulating moving reward penalties. Also, when the protagonist is at the extreme bottom of the grid (far from both the lava and the goal), the perturbation probability drops below 0:05 (the natural environment randomness), meaning that the antagonist tends to give more leverage to the protagonist in this region. The antagonist does this in order to recover its budget to get more powerful when the protagonist gets closer to the goal. (a) No antagonist ( = 1) (b) Perturbation budget In this work, we presented an adversarial game designed to compute risk-sensitive policies with respect to the Conditional Value-at-Risk (CVaR) risk measure. Our adversarial game is particular in the sense that it limits an antagonist’s perturbations to be within a specified budget and to only change next state transitions for a protagonist. We then presented a gradient-based algorithm based on the Stackelberg formulation of the game to solve it, 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 increasing the antagonist’s budget indeed leads a more cautious protagonist policy. 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.
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 our game to a concrete Sim2Real application to try and leverage the empirical potential of the method. Also, in light of the instability observed in our own empirical results, we would like to address the issue of sensibility to hyperparameters in our practical gradient-based algorithm.