{'fraction_non_alphanumeric': 0.03972294848860144, 'fraction_numerical': 0.009082152194853447, 'mean_word_length': 4.607510288065844, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantile-Based Policy Optimization for Reinforcement Learning

Classical reinforcement learning (RL) aims to optimize the expected cumulative rewards. In this work, we consider the RL setting where the goal is to optimize the quantile of the cumulative rewards. We parameterize the policy controlling actions by neural networks and propose a novel policy gradient algorithm called Quantile-Based Policy Optimization (QPO) and its variant Quantile-Based Proximal Policy Optimization (QPPO) to solve deep RL problems with quantile objectives. QPO uses two coupled iterations running at different time scales for simultaneously estimating quantiles and policy parameters and is shown to converge to the global optimal policy under certain conditions. Our numerical results demonstrate that the proposed algorithms outperform the existing baseline algorithms under the quantile criterion.


Introduction
In recent years, deep reinforcement learning (RL) has made significant achievements in games [1,2], robotic control [3], recommendation [4] and other fields. RL formulates a complex sequential decision-making task as a Markov Decision Process (MDP) and attempts to find an optimal policy by interacting with the environment. In the classical RL framework, the goal is to optimize an expected cumulative reward. However, expectation only reflects the average value of a distribution, but not the tail behavior. The tail of a distribution may capture catastrophic outcomes. For example, the joint defaults of many subprime mortgages * Corresponding author: pengyijie@pku.edu.cn led to the 2008 financial crisis, and in the post-crisis era, the Basel accord requires major financial institutes to maintain a minimal capital level for sustaining the loss under extreme market circumstances. In financial management, quantiles, also known as value-at-risk (VaR), can be directly translated into the minimal capital requirement.
Risk measures have been introduced into RL either in the forms of constraints or as the objectives, which are referred as risk-sensitivity RL in the literature. The tail behavior of the distribution can be better captured by risk measures, such as VaR and conditional value-at-risk (CVaR). With risk measures as the objective function of RL, the well-trained agent can be expected to perform more robustly under extreme events.
In this paper, we consider an RL setting where the goal is to optimize the quantiles of the cumulative rewards. In financial investment, investors may want to obtain the highest return subject to an acceptable level of risk; in system science, engineers may want to improve the system's most conservative output under extreme environment conditions. In Figure.1, although the mean values of the two distributions are the same, the 10%-quantile of distribution 1 is significantly larger than that of distribution 2. If the returns of two portfolios follow distributions 1 and 2, then it requires more capital to avoid bankruptcy in the presence of 90% possible returns for the second portfolio. For some distributions, e.g. the Cauchy distribution, expectation may not exist so that it cannot be used as a performance measure in this situation. In contrast, quantile are always well-defined.
We parameterize the policy controlling actions by neural networks. For RL learning problems where the dimension of the policy parameter is typically very high, gradientbased optimization provides a feasible approach. The gra- dient of quantiles can be expressed as a function of gradients of the distribution and quantile value. However, unlike an expectation, whose gradient can be estimated in a single simulation trajectory using techniques such as the likelihood ratio method, the gradient estimation for quantiles is much more complicated. We propose a novel policy gradient algorithm named Quantile-Based Policy Optimization (QPO) and its variant Quantile-Based Proximal Policy Optimization (QPPO) to solve deep RL problems with quantiles as objective. QPO uses two coupled iterations running at different time scales for simultaneously estimating quantiles and policy parameters and is shown to converge to the global optimal parameterized policy under certain conditions. Our proposed algorithms have been applied to financial investment examples, and numerical results demonstrate that the proposed algorithms outperform the existing baseline algorithms under the quantile criterion.

Mean-based RL
In RL with a mean-based criterion, there are two primary categories of methods. The first category is valuebased method, which learns a Q function and select the action with the best value. In deep RL, pioneer work includes Deep Q-learning (DQN) and its variants [1,5]. The second category is based on policy optimization, where the policy is parameterized by certain basis functions and optimized by stochastic gradient ascent. REINFORCE is an early policy gradient algorithm [6] . Trust Region Policy Optimization (TRPO) introduces the importance sampling technique into RL to improve data utilization efficiency [7]. By simplifying TRPO, Proximal Policy Optimization (PPO) achieves a significant improvement through optimizing a clipped surrogate objective and has become a commonly used baseline algorithm at present [8]. There are also some algorithms that combine the two categories, such as Deep Deterministic Policy Gradient (DDPG) and Soft Actor-Critic (SAC) [9,10].

Gradient Estimation of Risk Measure
Gradient estimation of risk measures has been studied actively. Classic gradient estimation problem considers expectation [11], whereas estimating gradients of quantile and CVaR is much more complicated. To address the difficulties, different methods, such as infinite perturbation analysis [12,13], kernel estimation [14,15], and measure-valued differentiation [16], have been developed. Recently, [17] uses generalized likelihood ratio estimators to estimate the gradient for a rather general distortion risk measure. However, these methods would require analytic forms of transition probabilities or rewards in the MDP, which is typically not satisfied in the RL setting. A well-known black-box gradient estimation approach is Simultaneous Perturbation Stochastic Approximation (SPSA) [18]. However, tuning parameters such as the perturbation size and step size in optimization require care and it is typically hard to apply SPSA to high-dimensional optimization such as our deep RL problems where the policy is parameterized by neural networks.

Risk-sensitive RL
Risk-sensitive RL has recently gained steam. One can use a risk measure as the objective function of RL. For example, expected exponential utility is used as the objective in [19]; [20] and [21] have studied CVaR-based objectives; [22] aims to optimize several variance-related risk measures by SPSA and a smooth function approach; [23] applies SPSA to optimize an objective function in the cumulative prospect theory.
One can also impose a risk measure as the constraint of a RL problem. For example, dynamic and time-consistent risk constraints are considered in [24]; [25] uses CVaR as the constraint; [26] develops policy gradient and actor-critic algorithms under VaR and CVaR constraints. A Lagrangian approach has been used to solve the RL problem subject to some risk measures [27]. Tuning a multi-scale iterative algorithm to update Lagrange multipliers requires care.
To the best of our knowledge, our work is the first to propose a two-time-scale iterative algorithm to optimize quantiles, which can be applied to large-scale optimization for policy parameterized by neural networks in deep RL problems.
The rest of the paper is organized as follows: In Section 3, we describe the MDP settings, the classical framework of policy gradient algorithms, and our quantile optimization framework for RL. Section 4 introduces our new algorithms called QPO and its variant QPPO. In Section 5, we establish the convergence to the global optimum for QPO. Numerical reuslts are presented in Section 6. We conclude the paper and discuss future direction in Section 7.

Markov Decision Process
A Markov Decision Process (MDP) can be represented as a 5-tuple (S, A, p, u, η), where S and A are state and action spaces, respectively; p(s |s, a) is the transition probability; u(s , a, s) is the reward function; η ∈ (0, 1) is the reward discount factor. One may expect to optimize a parameterized policy function π(a|s; θ), which is a distribution of the action conditional on the state, through the interaction with the MDP system. We denote the state and action at time t ∈ {0, 1, 2, · · · , T } by s t and a t , where s t ∼ p(·|s t−1 , a t−1 ) and a t ∼ π(·|s t ; θ). Then the trajectory generated by the MDP can be defined as In an episode, a complete simulation trajectory of the action and state is generated by the interaction between the agent and environment.

Mean-based Criterion for RL
In the classical setting, the objective function of RL algorithms is to maximize the expected cumulative reward: Policy gradient methods, an important class of RL algorithms, solve problem (1) by the stochastic gradient ascent.
The key for implementing policy gradient methods is to estimate gradient, and the likelihood ratio method is a popular stochastic gradient estimation technique. Specifically, the gradient can be expressed as below: where the interchange of the gradient and integral in the second equality can be justified by the dominated convergence theorem. The term U (τ ) T −1 t=0 ∇ θ log π(a t |s t ; θ) inside the expectation on the right hand side of (2) is an unbiased stochastic gradient estimation of ∇ θ E[U (τ )].
We assume that F R (r; θ) is continuously differentiable on R, i.e. F R (r; θ) ∈ C 1 (R), so that the α-quantile can be written as an inverse of the distribution function q(α; θ) = F −1 R (α; θ). Our goal is to maximize the α-quantile of the distribution on a compact convex set Θ ⊂ R m , i.e., To solve problem (3), we consider a stochastic gradient ascent method. By definition, F R (q(α; θ); θ) = α. Taking gradients on both sides with respect to θ, we have There are two difficulties for obtaining a single-run unbiased stochastic gradient estimator: • The right hand side of equality (4) contains the αquantile itself. The quantile would change in the sequential update of θ.
• The density function f R (·; θ) of the cumulative reward usually does not have an analytical form. We , but the gradient and expectation operators cannot be interchanged since 1{R ≤ r} is discontinuous.

Quantile-Based Policy Optimization
In this section, we propose a new on-policy RL algorithm, named Quantile-based Policy Optimization (QPO) algorithm and its variant Quantile-based Proximal Policy Optimization (QPPO) algorithm to solve the MDP with quantile criterion (3). The computation complexity of our algorithms will also be discussed.

Quantile Optimization of REINFORCE Style
Since the denominator of the α-quantile in equality (4) is non-negative, the ascent direction can be simplified as d = −∇ θ F R (r; θ) r=q(α;θ) in searching for the optimum. The likelihood ratio technique in (2) can be applied analogously to derive the gradient ∇ θ F R (r; θ) as below: ∇ θ log π(a n t |s n t ; θ).
We propose a two-time-scale iterative algorithm as follows: where ϕ(·) is a projection function to guarantee θ k ∈ Θ.
Recursion (5) is used to track the quantile of the current policy π(·|·; θ k ), i.e., a one-step search for the root of In practice, we divide D(τ k ; θ k , q k ) by the estimator of f R (q k ; θ k ) to speed up searching for the optimum. Here we offer two feasible approaches. One is to estimate the density by the empirical reward distribution. Using the wellknown Kernel Density Estimation (KDE) approach [28,29], we may construct the reward density function by a batch of episodes between two steps updating the parameters. An alternative approach is to approximate the indicator 1{·} by a smooth function that can be directly differentiated. For example, we have where σ(·) is the sigmoid function defined as σ(r; R) = 1 1 + e −(r−R) .
can be used as an estimator of f R (q k ; θ k ). We present the pseudo code of QPO in Algorithm 1 as follows.

Quantile Optimization of PPO Style
To improve data utilization efficiency and robustness, we propose a variant of our QPO algorithm by using an importance sampling technique inspired by PPO. We consider a pair of policy networks π(·|·; θ) and π(·|·;θ), where only π(·|·;θ) is used to interact with the environment. In each epoch, a batch of episodes are generated by following policy π(·|·;θ). Then, the target policy π(·|·; θ) is updated according to the episodes generated by π(·|·;θ), and the parameter θ is updated by the latest value of θ.
Thus, we can rewrite recursions (5) and (6) as follows: In practice, the gradient term ρ(τ k )D(τ k ; θ k , q k ) can be calculated stepwisely, which is computationally more efficient. If −1{U (τ k ) ≤ q k } is used as the advantage function A k t for each actionã k t in the trajectoryτ k , then the searching direction in recursion (9) can be replaced bŷ which can be obtained by differentiating the following surrogate objective: To constrain the difference between θ andθ, we introduce a clip function clip(x, x − , x + ), where x − and x + are the lower and upper truncation bounds. The clipped surrogate objective iŝ The pseudo code of QPPO is presented in Algorithm 2. To achieve a more stable performance, one may use an extra baseline network B(s t |w) and take A t = −1{U (τ k ) ≤ q k }−B(s t |w) as a new advantage function, where B(s t |w) is updated by minimizing the MSE of −1{u(τ k ) ≤ q k }.

Computation Complexity
We have proposed two new RL algorithms based on the quantile maximization criterion, which are counterparts of two corresponding mean-based algorithms, i.e., REIN-FORCE and PPO. The computational cost of calculating the stochastic gradient estimate for the policy parameter is comparable to that of the mean-based algorithms. The main difference is that our algorithms need to estimate the quantile of the current policy. Recursion (5) or (8) is a one-step iteration for the one-dimensional root searching problem, which is computationally very cheap. Compared with the corresponding mean-based algorithm, the increase in computation burden of QPO and QPPO is negligible.

Convergence Analysis
In this section, we establish the global convergence of the QPO algorithm. Let (Ω, F, P ) be a probability space. Define the filtration generated by our algorithm F k = {θ 0 , q 0 , · · · , θ k , q k } for k = 0, 1, · · · . Here we introduce some assumptions before the analysis.
Assumption A1 requires that the objective function is smooth enough, which is commonly assumed in continuous optimization. Assumptions A2 and A3 are standard in stochastic approximation analysis. Assumption A4 is necessary to avoid computational overflow.
If θ * = arg max θ∈Θ q(α; θ) is the unique global asymptotically stable equilibrium of this ODE, then the global convergence of QPO to θ * can be proved. Therefore, we first establish the unique global asymptotically stable equilibriums for ODE (12) and (13).
Next we proves that the sequence {q k } is almost surely bounded under our assumptions. The conditions in Theorem 1 will be verified in Theorem 2.
Proof. With F R (r; θ) ∈ C 1 (R) and A2, we have g 1 (q, θ) and g 2 (q, θ) are Lipschitz continuous. It has been verified in Lemma is Lipschitz continuous on the compact set Θ and {q k } is bounded as shown in Lemma 3, By noticing E[δ i |F i ] = 0, A3(a), and a similar argument in Lemma 3, we can prove {M k } is a L 2 -bounded martingale sequence, which implies that {M k } is bounded w.p.1.
With Assumption A3 and the conclusions in Lemmas 1 and 3, all conditions in Theorem 1 are satisfied. Therefore, it is almost sure that recursions (5) and (6) converge to the unique global asymptotically stable equilibrium of ODE (13), which is the optimal solution of problem (3) by the conclusion of Lemma 2.

Experiments
In this section, we conduct simulation experiments on different RL tasks to compare our QPO and QPPO with baseline RL algorithms REINFORCE and PPO. By experiments, we find that the SPSA-based algorithms can not train neural networks in the deep RL settings, so they are not compared with our methods.
The selection of {β k } will affect the convergence speed of the algorithm. We propose an adaptive updating approach for {β k }: where λ ∈ (0.5, 1), and c 0 , c 1 and c 2 are positive constants. The chosen {β k } satisfies the assumption A3(b). The rationale of this learning rate is to scale up the searching step by the magnitude of the current quantile estimate clipped by some upper-and-lower bounds. In practice, to speed up searching further, k −λ can be replaced by a factor that decays at a constant rate after certain number of iterations.

Toy Example: Zero Mean
In a simulation environment with T time steps, the reward of an agent at the t-th step is where δ t is an implicit system parameter vector controlled by the agent, and h(δ t ) is an explicit state vector that can be observed. Then R t follows a bimodal distribution with zero mean. Therefore, optimizing the expected cumulative reward is ineffective, whereas the quantile performance can be optimized by controlling δ t .  The learning curves of REINFORCE, QPO, PPO and QPPO are presented in Figure 3. The policy is represented by a neural network consisting of two hidden layers with each containing 32 neurons. The initial learning rate is set as 5 × 10 −4 , and it is multiplied by a decay factor 0.7 every 400 episodes. On the left hand side of the figure, we present the quantile estimated by total rewards in past 20 episodes. On the right hand side of the figure, we present the true quantiles estimated by 50 replications per 25 episodes. We can see that QPO and QPPO significantly improve the agent's quantile performance. In contrast, the learning curves of RINFORCE and PPO keep oscillating around a low level.

Stock Trading with Simulated Prices: Sim Stock
We consider a simplified stock trading problem with N simulated stock prices and T time steps, where high returns are associated with high risks. The price of every stock is generated independently beforehand by a model in [33]. For the n-th stock, the log price x t+1 at time t + 1 is where η 1 and η 2 are constants, ε n t and v n t are noises which follow a bimodal distribution, more specifically, a summation of a zero-mean normal random variable and zero-mean binomial random variable. A bimodal distribution can capture distinctive statistical characteristics of the price movements under bull and bear market scenarios. Then the price sequences {p n t } are simulated by The agent initially holds a random portfolio with a fixed total value 1 and can control the proportion of cash invested into each stock. At every time step, the agent first makes investment decisions, and calculates the total value of the portfolio under current stock prices and that under new stock prices. The agent is rewarded by the differences of two total values. In addition, cash held by the agent offers 0.2% risk-free return per time step. The observation state contains stock prices at the past few steps and the current portfolio.  The learning curves of REINFORCE, QPO and QPPO are presented in Figure 4. The policy and the baseline are represented by neural networks consisting of two hidden layers with each containing 64 neurons. The initial learning rate is set as 5 × 10 −4 , and it is multiplied by a decay factor 0.7 every 500 episodes. The agent invests into 8 stocks in 200 time steps and can look back at stock prices within the past 5 steps. On the left hand side of the figure, we present the quantile estimated by total rewards in past 20 episodes. On the right hand side of the figure, we present the true quantiles estimated by 20 replications per 25 episodes.
Better quantile performance of the portfolio indicates that it is more robust under extreme market scenarios. The two quantile-based algorithms QPO and QPPO achieve much superior quantile performances than the mean-based algorithm REINFORCE in this example. In addition, QPPO converges faster than QPO.

Stock Trading with Real Prices: Dow Stock
We replace the simulated stock prices with the real data of Dow Jones 30 in [34] and use the metric 'prccd' as a proxy of daily prices for the real stock market. We conduct experiments under the same setting as in simulated stock prices.  The learning curves for REINFORCE, QPO and QPPO are presented in Figure 4. In this example, QPO and QPPO still outperform the REINFORCE algorithm. QPPO converges faster than QPO at the beginning, but it lags slightly behind the latter at the end. This phenomenon may be attributed to the baseline network introduced in QPPO. Although baselines can speed up the convergence of policybased algorithms, they also introduce biases. Unlike the mean-based baseline in PPO, the quantile-based baseline is not centralized so that it tends to be more difficult to learn.

Conclusion
In this paper, we propose a QPO algorithm and its variant QPPO for RL with a quantile criterion under a policy optimization framework. To the best of our knowledge, this is the first deep RL algorithm that directly optimizes quantile performance. We prove that QPO converges to the global optimum under certain conditions. The numerical experiments show that our proposed algorithms are effective for optimizing policy with a quantile criterion. In future work, the criterion can be extended to the distortion risk measure which is more general than quantiles. How to combine the quantile criterion with more effective policy optimization algorithms also deserves further study.